Type class instance can't be found for type lambda, but type alias works

[scabug]

Suppose we have the following two type classes, an instance of the first for an either-like trait, and a way of building instances of the first from some specific instances of the second:

trait Foo[F[_]]
trait Bar[F[_], A]

trait Or[A, B]

implicit def orFoo[A] = new Foo[({type L[X] = Or[A, X]})#L] {}
implicit def barFoo[F[_]: Foo] = new Foo[({type L[X] = Bar[F, X]})#L] {}

Now we can define a couple of type aliases:

type StringOr[X] = Or[String, X]
type BarStringOr[X] = Bar[StringOr, X]

And get an instance of our first type class:

scala> implicitly[Foo[BarStringOr]]
res1: Foo[BarStringOr] = $anon$1@4b5a1133

But when we try the same thing with a type lambda, we get an error:

scala> implicitly[Foo[({type L[X] = Bar[StringOr, X]})#L]]
<console>:14: error: could not find implicit value for parameter e: Foo[[X]Bar[[X]Or[String,X],X]]
              implicitly[Foo[({type L[X] = Bar[StringOr, X]})#L]]
                        ^

I asked a question on Stack Overflow about this last week, but haven't gotten any answers, and I haven't been able to find any previous issues that address the problem (a comment on my question points to this open improvement, but I don't see how this could be a type constructor inference issue).

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-6895?orig=1
Reporter: Travis Brown (travisbrown)
Affected Versions: 2.9.2, 2.10.0
See #2712

[scabug]

@paulp said (edited on Dec 31, 2012 10:23:25 AM UTC):
Type lambdas are cool and all, but not a single line of the compiler was ever written with them in mind. They're just not going to work right: the relevant code is not robust. I spent a day or so looking at #5294 not long ago and it was too hard to fix; this is probably a duplicate. I doubt there are more than three people right now with any chance of fixing this stuff and all of us have a bunch of higher priorities, so if this is important to you I suggest rolling up your sleeves (this would be in the "way, way up" position) and seeing what you can do.

[scabug]

Erik Westra (eecolor) said:
More examples of (probably) this error can be seen at: http://stackoverflow.com/questions/24783289/could-not-find-implicit-value-for-evidence-parameter-of-type-scalaz-applicative/24944552#24944552

[scabug]

@retronym said:
Here's a cut down reproduction.

trait Foo[F1[_]]
trait Bar[F2[_]]
 
class Test {
  def barFoo[F3[_]]: Foo[F3] = ???

  // Now we can define a couple of type aliases:
  type M[X1] = String
  type N[X2] = Bar[M]

  // val ok1: Foo[N] = barFoo
  // val ok2: Foo[({type L[X] = Bar[M]})#L] = barFoo[N]
  val nok: Foo[({type L[X3] = Bar[M]})#L] = barFoo /* Type inference can't unify F with L */
}

[scabug]

@retronym said:
I've analysed this further and realised that this is not a bug, but rather a manifestation of the limitation of higher kinded inference, #2712.

I've submitted my analysis as a test case: scala/scala#4569