Get the "most specific" input type

Question

Suppose I have a function-like type e.g.

trait Parser[-Context, +Out]

and I want to be able to combine multiple parsers such that the combined Context will be the most-specific type among the combined parsers' contexts. For example:

Parser[Any, Int] + Parser[String, Long] = Parser[String, (Int, Long)]
Parser[String, Int] + Parser[Any, Long] = Parser[String, (Int, Long)]
Parser[Option[Int], Foo] + Parser[Some[Int], Bar] = Parser[Some[Int], (Foo, Bar)]
Parser[String, Foo] + Parser[Int, Bar] = <should be a compile error>

To put the example in more concrete terms, suppose I have a function combiner like

def zipFuncs[A, B1, B2](f1: A => B1, f2: A => B2): A => (B1, B2) = {
  a => (f1(a), f2(a))
}

and some functions like

val f1 = { a: Any => 123 }
val f2 = { a: String => 123 }
val f3 = { a: Option[Int] => 123 }

Now I can do

> zipFuncs(f1, f2)
res1: String => (Int, Int) = <function>

> zipFuncs(f1, f3)
res2: Option[Int] => (Int, Int) = <function>

> zipFuncs(f2, f3)
res3: Option[Int] with String => (Int, Int) = <function1>

But what I want is for zipFuncs(f2, f3) to not compile at all. Since String is not a subtype of Option[Int], and Option[Int] is not a subtype of String, there's no way to construct an input value for res3.

I did create a typeclass:

// this says type `T` is the most specific type between `T1` and `T2`
sealed trait MostSpecificType[T, T1, T2] extends (T => (T1, T2))
// implementation of `object MostSpecificType` omitted

def zipFuncs[A, A1, A2, B1, B2](f1: A1 => B1, f2: A2 => B2)(
  implicit mst: MostSpecificType[A, A1, A2]
): A => (B1, B2) = { a: A =>
  val (a1, a2) = mst(a)
  f1(a1) -> f2(a2)
}

This accomplishes the goal described above, but with a really annoying problem. IntelliJ will highlight valid combinations as errors, inferring that the "most specific type (A)" is actually Nothing when it is in fact a real value. Here's the actual issue in practice.

The highlighting issue is surely a bug in IntelliJ, and google searching seems to imply that various resets/cache wipes/etc should fix it (it didn't). Regardless of the blame, I'm hoping to find an alternate approach that both satisfies my original requirement, and doesn't confuse IntelliJ.

score 4 · Answer 1 · edited May 23 '17 at 10:30

You can achieve that using generalized type constraints:

def zipFuncs[A1, A2, B1, B2](f1: A1 => B1, f2: A2 => B2)
                            (implicit ev: A2 <:< A1): A2 => (B1, B2) = {
  a => (f1(a), f2(a))
}

val f1 = { a: Any => 123 }
val f2 = { a: String => 123 }
val f3 = { a: Option[Int] => 123 }

zipFuncs(f1, f2) // works
zipFuncs(f1, f3) // works
zipFuncs(f2, f3) // cannot prove that Option[Int] <:< String

However, this requires the second function to use a more specific type in the input parameter than the first one. This is OK unless you also want zipFuncs(f2, f1) to work too. If you do have that requirement, I don't see any other way than doing some implicit type gymnastics similar to the ones you already do.

EDIT: See Eduardo's answer for a neat trick on achieving this.

And yes, I also had a number of situations when IntelliJ sees something as an error when in fact it is not. I know it's tedious but I don't see a way to fix the situation other than reporting an issue and waiting.

Cheers for the response. Glad to know I'm not the only one having highlighter issues, but sad that it's a problem at all. I did have "that requirement" which is why I ultimately accepted Eduardo's answer, but +1 for taking the time — Dylan, Nov 29 '16 at 22:26
No probs. If someone has no clue about generalized type constraints, I think my answer is a bit easier to see the idea before checking out how @Eduardo used them (along with some extra tricks) to make the whole thing work :) — slouc, Nov 29 '16 at 22:30

score 2 · Accepted Answer · answered Nov 29 '16 at 22:18

If you want this to work only when one of the types is a subtype of the other, then you can do this:

def Zip[A,X,Y](f: A => X, g: A => Y): A => (X,Y) = a => (f(a), g(a))

implicit class ZipOps[A,X](val f: A => X) extends AnyVal {

  def zip[A0, Y](g: A0 => Y)(implicit ev: A0 <:< A): A0 => (X,Y) = 
    Zip({a: A0 => f(a)},g)

  def zip[A0 >: A, Y](g: A0 => Y): A => (X,Y) = 
    Zip(f,g)

}

val f1: Any => Int = { a: Any => 123 }
val f2: String => Int = { a: String => 123 }
val f3: Option[Int] => Int = { a: Option[Int] => 123 }

val x1 = f1 zip f2 // works
val x1swap = f2 zip f1 // works
val x2 = f1 zip f3 // works
val x3 = f2 zip f3 // cannot prove that Option[Int] <:< String
val x3swap = f3 zip f2 // cannot prove that String <:< Option[Int]

That is exactly the behavior I was looking for. I'll have to try this approach out in my actual project! — Dylan, Nov 29 '16 at 22:28

Get the "most specific" input type

2 Answers2