type aliases breaking implicit resolution

[fommil]

in scalaz (but also in cats)

scala> import scalaz._, Scalaz._

scala> val valids: List[ValidationNel[Int, String]] = List(1.failureNel[String], "hello".successNel[Int])
valids: List[scalaz.ValidationNel[Int,String]] = List(Failure(NonEmpty[1]), Success(hello))

scala> valids.separate
<console>:22: error: could not find implicit value for parameter G: scalaz.Bifoldable[G]
       valids.separate
              ^

scala> val valids: List[Validation[NonEmptyList[Int], String]] = List(1.failureNel[String], "hello".successNel[Int])
valids: List[scalaz.Validation[scalaz.NonEmptyList[Int],String]] = List(Failure(NonEmpty[1]), Success(hello))

scala> valids.separate
res2: (List[scalaz.NonEmptyList[Int]], List[String]) = (List(NonEmpty[1]),List(hello))

note that the code is identical in both but the first code is using the type alias ValidationNel[..., ...], and the second is using raw type Validation[NonEmptyList[...], ...]

[tpolecat]

I chatted with @fommil about this and it is with -Ypartial-unification turned on.

@milessabin is this surprising? I kind of expected it to be opaque to aliasing. Or maybe this has nothing to do with -Ypartial-unification.

[milessabin]

Could you try and put together a small self-contained reproduction?

[tpolecat]

Now that I look at it more closely the problem is that the shapes are different.

type F[A, B] = Validation[A, B]
type G[A, B] = Validation[NonEmptyList[A], B]

Or, to simplify

type F[A] = List[A]
type G[A] = List[Option[A]]

The first has an implicit functor for instance, but the second doesn't.

So I think this is expected behavior.

[milessabin]

Happy for me to close this?

[fommil]

I don't believe this is "expected" behaviour. What would be the negative consequences of implicit resolution doing a final step where all types are dealiased?

[fommil]

It's not clear when this will or won't resolve... e.g. this works

scala> type ListO[A] = List[Option[A]]
defined type alias ListO
scala> trait Implicit[A]
defined trait Implicit
scala> implicit def ilo[A]: Implicit[ListO[A]] = null
ilo: [A]=> Implicit[ListO[A]]

scala> implicitly[Implicit[ListO[String]]]
res = null
scala> implicitly[Implicit[List[Option[String]]]]
res = null

[eparejatobes]

There are several issues related with aliases and implicit resolution/inference: #5070, #8740, #8709.

This #8709 (comment) could point to something variance-related (at least in the scalaz case); NonEmptyList is invariant, Validation covariant.

[retronym]

Thanks for pushing the branch with the reproduction.

I believe this is an faithful minimization:

abstract class C {
  type V[A]
  type N[A]
  type VN[A] = V[N[A]]

  type TC1[_[_]]
  type TC2[_]

  def infer[M[_], A](ma: M[A])(implicit M: TC1[M], A: TC2[A]) = ???

  def  ok1(vn: V[N[Int]])(implicit V: TC1[V], NInt: TC2[N[Int]]) = infer(vn)
  def nok1(vn:  VN[Int] )(implicit V: TC1[V], NInt: TC2[N[Int]]) = infer(vn)
  def  ok2(vn:  VN[Int] )(implicit V: TC1[V], NInt: TC2[N[Int]]) = infer(vn : V[N[Int]])

}

In nok1, the application of infer(vn) is typechecked to C.this.infer[C.this.VN, Int](vn) before any implicit search for the implicit args of infer is undertaken. The subsequent implicit search fails.

The inferred type argument for infer is not the only possibility, by looking that the chain of dealiasing of the type of vn (which is the input the drives this inference in this spot), you could also come up with M=V, A=N[Int], which would have steered things towards a successful implicit search.

The Scala typechecker doesn't support backtracking, so dealiasing (and base-typing) is only done to get to the first plausible unification. I suspect that backtracking would be computationally unfeasible, remembering that method type parameter inference also occurs for the candidate expressions to satisfy implicit arguments, and so on recursively. So even just a branching factor of 2 in the search can cause a blowup of 2^N in the implicit search time, where N is the depth of the implicit search tree.

It would be interesting to think of ways to pose the problem of type parameter and implicit term inference in some sort of unified way that might lend itself to a computationally feasible search. But I don't see anything we can do in the meantime to make this work as you'd hope.

[fommil]

Thanks for finding the core problem. How about workarounds where we could somehow indicate to the compiler that a certain implicit should be treated as having two names?

[dwijnand]

In scala/scala#7662 @adriaanm mentions:

implicits defined in packages are also being phased out

Does that change the feasibility of fixing this? In other words, should this be reopened as no longer "Won't Fix"?