Higher kinded existentials without covariant annotation

Question

When trying to use higher kinded existentials in Scala I run into the following problem:

trait A[H[_]]
trait Test {
  val l: A[List]
  // [error] type mismatch;
  // [error]  found   : A[List]
  // [error]  required: A[_[_] <: Any]
  // [error] Note: List <: Any, but trait A is invariant in type H.
  // [error] You may wish to define H as +H instead. (SLS 4.5)
  val x: A[B] forSome { type B[_] } = l
}

Adding a covariant annotation to H as the compiler suggests works. Is there a way to work around this if I don't want H to be covariant?

Answer 1

A slight variation of the example gives a more helpful error message:

scala> l: (A[B] forSome { type B[_] })
<console>:10: error: type mismatch;
 found   : A[List]
 required: A[_[_] <: Any]
Note: List <: Any, but trait A is invariant in type H.
You may wish to define H as +H instead. (SLS 4.5)
              l: (A[B] forSome { type B[_] })
              ^
<console>:10: error: can't existentially abstract over parameterized type B
              l: (A[B] forSome { type B[_] })
               ^

Looking for this error brings us to a TODO in the compiler.

Since existential types are going to disappear, per Odersky's email, I don't think this limitation will be fixed. However, Martin Odersky's email also reminds us that existential types are equivalent to abstract types. Hence, the above example can be encoded as follows:

scala> trait A { type H[_] }
defined trait A

scala> val l: A {type H[X] = List[X]} = null
l: A{type H[X] = List[X]} = null

scala> l: A
res0: A = null

Type application is syntactically ugly, but turning a value into an existential becomes trivial (also to implement in a compiler, which is part of Odersky's point).

What's useful to encode existentials is that type members don't have to be instantiated ever. So, to encode A[_] we can write:

scala> class A { type T }
defined class A

scala> new A
res1: A = A@3a7049a6

What's confusing here is that this does not work for objects:

scala> object B { type T }
<console>:8: error: only classes can have declared but undefined members
       object B { type T }
                       ^

But I recently got that accepted as a bug — see here for a pull request clarifying the spec (approved by Adriaan Moors), and here for my bug report and one-line fix to the compiler (still waiting for review).