Scala type inference for existential types and typ

Question

The following piece of code does not compile :

trait A[F] {
  def find(x: Int): F
  def fill(f: F): Unit
}

object TestA {
  def test[T <: A[F] forSome { type F }](t: T) =
    t.fill(t.find(0))
}

It returns the following compilation error :

test.scala:8: error: type mismatch;
 found   : (some other)F(in type T)
 required: F(in type T)
    t.fill(t.find(0))
                 ^

However the following code complies just fine :

trait B[F] {
  type R = F
  def find(x: Int): R
  def fill(f: R): Unit
}

object TestB {
  def test[T <: B[F] forSome { type F }](t: T) =
    t.fill(t.find(0))
}

I have two questions here :

1. I expect the fist piece of code to compile. Why does it not?

2. If there is a good reason why first piece of code does not compile, I would expect the second to not compile either, for the same reason. How then, does it compile successfully?

Is either of these a bug?

Answer 1

I don't know why the compiler differentiates the two pieces of code. Basically, the code doesn't compile because the type returned by find and the type expected by fill don't have to be the same F, at least if find and fill were called on two different objects.

You could make the first piece of code to compile with:

def test[T <: A[F], F](t: T) =
  t.fill(t.find(0))

And you could make the second piece of code not to compile with:

def test[T <: B[F] forSome { type F }](t: T, u: T) =
  t.fill(u.find(0))

This should be rather a comment than an answer, but I don't have 50 reputation yet.

Answer 2

To understand what's happening, let's look at simpler versions of TestA.test and TestB.test.

object TestA {
  def test1(a: A[String]) = {
    val s: String = a.find(0)
    a.fill(s)
  }
}

object TestB {
  def test1(b: B[String]) = {
    val r: b.R = b.find(0)
    b.fill(r)
  }
}

Notice how the type of the intermediate value s refers to String, while the type of the intermediate value r does not.

object TestA {
  def test2(a: A[F] forSome {type F}) = {
    val s: F forSome {type F} = a.find(0)

    // type mismatch;
    //   found   : s.type (with underlying type F forSome { type F })
    //   required: F
    a.fill(s)
  }
}

object TestB {
  def test2(b: B[F] forSome {type F}) = {
    val r: b.R = b.find(0)
    b.fill(r)
  }
}

Once we throw in the existentials, we end up with an intermediate value s whose type is equivalent to Any, and which thus isn't a valid input for a.fill. The intermediate type for r, however, is still b.R, and so it is still an appropriate input for b.fill. The reason its type is still b.R is because b.R doesn't refer to F, and so according to the simplification rules for existential types, b.R forSome {type F} is equivalent to b.R, in the same way that Int forSome {type F} is equivalent to Int.

Is either of these a bug?

Well, there is certainly a bug somewhere (as of scalac 2.11.7), because the following does not type check.

object TestB {
  def test3(b: B[F] forSome {type F}) = {
    val r: b.R forSome {type F} = b.find(0)

    // type mismatch;
    //   found   : F
    //   required: b.R
    //     (which expands to)  F
    b.fill(r)
  }
}

So either I'm wrong to think that b.R does not refer to F, in which case b.R forSome {type F} is not equivalent to b.R and your TestB.test should not type check but it does, or b.R forSome {type F} is equivalalent to b.R, in which case my TestB.test3 should type check but it doesn't.

I'm quite convinced that the bug is with the latter, because the error even occurs when the existential quantification has nothing to do with b.R, as in the following example.

object TestB {
  def test4(b: B[F] forSome {type F}) = {
    val r: b.R forSome {val x: Int} = b.find(0)

    // type mismatch;
    //   found   : F
    //   required: b.R
    //     (which expands to)  F
    b.fill(r)
  }
}