With 2.7 of Scala on the way, people are being exposed to Java wildcards more and more, which translate to Scala existential types. Unfortunately no one seems to understand these (including me at first!) and had previously let them go largely ignored, and now everyone is getting confused.

Here’s a brief introduction.

scala> def foo(x : Array[Any]) = println(x.length);
foo: (Array[Any])Unit

scala> foo(Array[String]("foo", "bar", "baz"))
:6: error: type mismatch;
 found   : Array[String]
 required: Array[Any]
       foo(Array[String]("foo", "bar", "baz"))

This doesn’t compile, because an Array[String] is not an Array[Any]. You can put 1 into an Array[Any], but not into an Array[String]. Nonetheless, it’s completely typesafe – we’ve only used methods in foo which would work for any Array[T]. How do we fix this?

Here’s one way:

scala> def foo[T](x : Array[T]) = println(x.length)
foo: [T](Array[T])Unit

scala>> foo(Array[String]("foo", "bar", "baz"))
3

We’ve parameterised the method by T in order to make it accept any T. But now we have a superfluous type parameter on our method. This may not seem like a big deal, and it’s usually not, but it can add up if you’re not careful (and can be particularly annoying when for some reason the type checker is no longer able to infer a single one of your type parameters and you have to supply all of them). It’s also not really what we mean – we mean “I want an Array, and I don’t care what type of things it contains”

This is exactly what existential types are for.

scala> def foo(x : Array[T] forSome { type T}) = println(x.length)
foo: (Array[T] forSome { type T })Unit

scala> foo(Array[String]("foo", "bar", "baz"))
3

This is quite verbose, I know. There’s a shorthand, Array[_], but this has some unfortunate unintuitive behaviour. I’ll explain this later.

Sometimes we want to act on a more specific type, but don’t care exactly what type it is. For example suppose we wanted this to work on any CharSequence and do something more complicated to each argument. e.g.

scala> def foo(x : Array[T] forSome { type T <: CharSequence}) = x.foreach(y => println(y.length))
foo: (Array[T] forSome { type T <: java.lang.CharSequence })Unit

scala> foo(Array[String]("foo", "bar", "baz"))
3
3
3

The type arguments in an existential type can have upper and lower bounds like normal type declarations. They can't have view bounds, presumably due to technical limitations.

So we've seen how these are used, and that was relatively nonconfusing (I hope!). Let's pin down exactly what these mean.

Suppose we have a type constructor M. In other words, for a type T, M[T] is a type, but M is *not* itself a type. M could be List, Array, Class, etc. M[T] forSome { type T; } is the type of all things for which there is some T such that they are of type M[T]. So an Array[String] is of this type, because we can choose T = String, as is an Array[Int], etc.

If we add bounds, all we do is restrict the range that T can lie in. An Array[String] is not an Array[T] forSome { type T <: Number; } because the only possible choice of T (String) is not a subtype of Number

Now, all you need to do in order to understand a given existential type declaration is to apply this rule rigorously. But this can be hard, especially because precedence matters in subtle ways! I'll walk you through some examples.

T forSome { type T; }

This is the type of all things for which there exists some T such they are T. Wha?

Think about it for a second. It's the type of all things for which there exists a type such that they are of that type. i.e. it's a long winded way of writing the type of all things, Any. This is important, and it often trips people up when they write subtly the wrong thing. Considering the following two types:

Array[T] forSome { type T; }
Array[T forSome { type T; }]

They look almost identical, but they're in fact very different. The first is the type of all arrays, whatever their type parameter. The second is Array[Any]

Let's take another example, because this is the one which seems to come up a lot. We have a Map. We want it to map classes to something. Let's say Strings. What type do we use?

Here. Pick one:

Map[Class[T forSome { type T}], String]
Map[Class[T] forSome { type T}, String]
Map[Class[T], String] forSome { type T}

Which did you pick?

The correct answer is "Map[Class[T] forSome { type T}, String]", or to save you searching for ]s, "the middle one".

Why? Well, the first one is a Map[Class[Any], String]. Class is invariant in its type parameters. So the only Class[Any] is in fact classOf[Any] (this is basically the same as Object.class in Java). So that's not very useful. Similarily, the third one is the supertype of all map types such that there is some T such that they are a Map[Class[T], String]. So again, we've got some fixed class type for keys in the map - it's just that this time we don't know what type it is. The middle one however has keys of type Class[T] forSome { type T }. That is, its keys are classes which are allowed to have any value they want for their type parameter. So this is what we actually wanted.

Now, the final confusing point. As I mentioned, we have this shorthand use of _ for wildcards. So we can write Array[_] to mean Array[T] forSome { type T}. That's nice. So what happens if we try to use this in the above and write Map[Class[_], String]? It turns out, we get "Map[Class[T], String] forSome { type T}". The wildcards always bind to the outermost level of the type expression. This is, unfortunately, almost never what you want in cases where it affects anything. There's been some discussion about changing it. I don't know if it will go anywhere.

Anyway, hopefully this has made some sense of things for you. It's a really confusing subject when you first encounter it, but once you've got it straight in your head it's not too bad. It would be nice if it could be simpler, but I'm not really sure what the best way to do this actually would be.