Distinction between type aliases and type lambdas

Question

This question is about a limitation of Scala's implicit resolution system that I've run into a few times when using Scalaz and that doesn't make a lot of sense to me. I've distilled the problem to a Scalaz-less version below, but I'm happy to provide more information about motivation if needed.

Suppose I have a couple of type classes that witness something about a type constructor:

import scala.language.higherKinds

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

Now also suppose that if I have a Foo instance for some F, I know I also have a Foo instance for Bar[F, _]:

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

I've also got instances for List and the right side of Either:

implicit object listFoo extends Foo[List]
implicit def eitherFoo[A] = new Foo[({type L[X] = Either[A, X]})#L] {}

Now it's pretty clear that I should be able to write the following:

type BarList[X] = Bar[List, X]

implicitly[Foo[BarList]]

Or, equivalently:

implicitly[Foo[({type L[X] = Bar[List, X]})#L]]

And indeed, both work exactly as expected.

So I try the following:

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

And then:

scala> implicitly[Foo[BarStringOr]]
res2: Foo[BarStringOr] = $anon$1@39a6c855

Again, no surprises here. But then I try:

implicitly[Foo[({type L[X] = Bar[StringOr, X]})#L]]

And I get the following:

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

Note that I have no problem inferring the necessary Foo instance for StringOr, or calling barFoo explicitly to get the desired instance:

scala> implicitly[Foo[StringOr]]
res4: Foo[StringOr] = $anon$1@3eaac006

scala> barFoo[StringOr]
res5: Foo[[X]Bar[StringOr,X]] = $anon$1@179fbfea

I'm having trouble identifying what important distinction there could be between the List and StringOr cases that allows the type lambda version to work for the former but not the latter.

I've tried this on Scala 2.10.0-RC5 and 2.9.2. Adding covariance throughout doesn't help.

Am I missing something obvious? Can someone point me to something in the spec that would help me make sense of this, or to previous discussions of similar issues?

Answer 1

OK, I'm not 100% sure, but I think we can make some progress by reducing this to the simplest possible case that fails. Implicits are not the issue here, nor are type aliases. This is enough to fail:

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

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

val res1: Foo[({type L[X] = Either[String, X]})#L] = null

val works = barFoo[({type L[X] = Either[String, X]})#L](res1)
val fails = barFoo(res1)

The issue issems to be Scala's inabality to infer the type argument for barFoo as [X]Either[java.lang.String,X]. This seems to due to (or at least related to) to scalac's refusal to infer a partially applied type constructor.

(On a related note, this is an example of one of those types that Scala consideres unacceptably complex).