Implicit search fails to expand type alias

[scabug]

I encountered this error when using scalaz 6.0.4, and here is a self-contained test case:

class AliasBug { 

  type ValidationNEL[E, X] = Validation[NonEmptyList[E], X]

  def success[E, A](a: A): Validation[E, A] = Success(a)

  def failure[E, A](e: E): Validation[E, A] = Failure(e)

  def validation[E, A](e: Either[E, A]): Validation[E, A] = e.fold(Failure(_), Success(_))

  implicit def mab[M[_, _], A, B](a: M[A, B]): MAB[M, A, B] = new MAB[M, A, B] {
    val value = a
  }

  implicit def ValidationBifunctor: Bifunctor[Validation] = new Bifunctor[Validation] {
    def bimap[A, B, C, D](k: Validation[A, B], f: A => C, g: B => D) =
      k match {
        case Failure(a) => failure(f(a))
        case Success(b) => success(g(b))
      }
  }

  val validated: ValidationNEL[ErrorDetails,String] = ???

  // Doesn't compile
  validated.<-:(details => details)

  // Does compile
  //val temp: Validation[NonEmptyList[ErrorDetails],String] = validated
  //temp.<-:(details => details)

}

class ErrorDetails {}

sealed trait NonEmptyList[+A] {
  val head: A
  val tail: List[A]
}

sealed trait Validation[+E, +A] {}
final case class Success[E, A](a: A) extends Validation[E, A]
final case class Failure[E, A](e: E) extends Validation[E, A]

sealed trait MAB[M[_, _], A, B] extends PimpedType[M[A, B]] with MA[({type λ[X]=M[A,X]})#λ, B] {
  def bimap[C, D](f: A => C, g: B => D)(implicit b: Bifunctor[M]): M[C, D] = b.bimap(value, f, g)

  def <-:[C](f: A => C)(implicit b: Bifunctor[M]): M[C, B] = b.bimap(value, f, identity[B])
}

trait MA[M[_], A] extends PimpedType[M[A]]

trait PimpedType[X] {
  val value: X
}

trait Bifunctor[F[_, _]] {
  def bimap[A, B, C, D](k: F[A, B], f: A => C, g: B => D): F[C, D]
}

[scabug]

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

[scabug]

@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

[scabug]

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.

[scabug]

@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].

[scabug]

@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]).