[SI-8286] Implicit search fails to expand type alias Created: 14/Feb/14  Updated: 14/Feb/14

Status: Open
Project: Scala Programming Language
Component/s: Type Inference
Affects Version/s: Scala 2.8.1, Scala 2.9.3, Scala 2.10.3, Scala 2.11.0-M8
Fix Version/s: None

Type: Bug Priority: Minor
Reporter: Robin Green Assignee: Jason Zaugg
Resolution: Unresolved Votes: 1
Labels: None

Issue Links:
Duplicate
duplicates SI-6948 unification should consider all parents Open
Relates
relates to SI-6948 unification should consider all parents Open
relates to SI-2712 implement higher-order unification fo... CLOSED

 Description   

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]
}



 Comments   
Comment by Jason Zaugg [ 14/Feb/14 ]

Thanks for the standalone test case.

This is actually just a duplicate of SI-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

Comment by Robin Green [ 14/Feb/14 ]

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.

Comment by Jason Zaugg [ 14/Feb/14 ]

Sorry, my bad. It's related to that ticket, but not identical. It's actually another instance of https://issues.scala-lang.org/browse/SI-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]`.

Comment by Jason Zaugg [ 14/Feb/14 ]

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

Generated at Tue Aug 14 18:30:25 CEST 2018 using JIRA 7.9.1#79001-sha1:60970b42586a2ec2760ed6cfe825b26961e62b9e.