Imported From: https://issues.scala-lang.org/browse/SI-8286?orig=1
Reporter: Robin Green (greenrd)
Affected Versions: 2.8.1, 2.9.3, 2.10.3, 2.11.0-M8
See #6948, #2712
Duplicates #6948

@retronym said (edited on Feb 14, 2014 3:57:19 PM UTC):
Thanks for the standalone test case.

This is actually just a duplicate of #2712.

The type alias serves to help type constructor inference know how you want to partially apply the binary type constructor ValidationNel to conform to the expected kind M[_].

I tried to explain the behaviour recently: https://gist.github.com/puffnfresh/8540756#comment-991433

Robin Green (greenrd) said:
I don't follow. In this bug, the type alias is what causes the bug to occur. It doesn't help anything. Also, there's only one type alias here, and that's ValidationNel.

@retronym said:
Sorry, my bad. It's related to that ticket, but not identical. It's actually another instance of #6948

It comes down to the way the Scala infers:

object Test {
  def foo[M[_, _]](m: M[_, _]) = 0
  val x: (Option[Int], Int) = (None, 0)
  foo(x)
  type T[A, B] = (Option[A], B)
  foo(x: T[Int, Int])
}

% qbin/scalac -Xprint:typer sandbox/test.scala
[[syntax trees at end of                     typer]] // test.scala
package <empty> {
  object Test extends scala.AnyRef {
    def <init>(): Test.type = {
      Test.super.<init>();
      ()
    };
    def foo[M[_, _] >: [_, _]Nothing <: [_, _]Any](m: M[_, _]): Int = 0;
    private[this] val x: (Option[Int], Int) = scala.Tuple2.apply[None.type, Int](scala.None, 0);
    <stable> <accessor> def x: (Option[Int], Int) = Test.this.x;
    Test.this.foo[Tuple2](Test.this.x);
    type T[A, B] = (Option[A], B);
    Test.this.foo[Test.T]((Test.this.x: Test.T[Int,Int]))
  }
}

Type constructor inference looks at stream of dealiased- and base-types for the argument in search for one of the right kind. By introducing the alias above, it infers foo[T] rather than foo[Tuple2]. In your example, this doesn't line up with the available implicits. No backtracking is tried to dealias.

Workarounds are to provide implicit type class instances like implicit def ValidationNELBifunctor: Bifunctor[ValidationNEL], or to manually provide type arguments.

You could also use

type ValidationNelString[A] = ValidationNel[String, A]

This has a different kind, so it will be dealised when trying to unify ValidationNelString[X] with M[A, B].

@retronym said:
The tension here arises from not having an unambiguous kind for a given type; both subtyping and type aliases mean that a type can be interpreted as having a variety of kinds. This is at odds with inference.

Haskell can do a better job here, for example, as it doesn't have subtyping, and it also mandates that partially applied type constructors can only be applied in declaration order (e.g. Tuple[Int, Int] can be considered as ([B]=>Tuple[Int, B])[Int]), but not ([A]=>Tuple[A, Int])[Int]).