Existential types in Scala

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 typeM[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.

This entry was posted in programming and tagged , , on by .

15 thoughts on “Existential types in Scala”

1. Henry Ware

Hi David,

Nice post, it helped straighten me out, I think.

The paragraph with the quiz answers seems muddled— you meant third when you said second, right?

2. Mateusz

I think this article is very useful. However I’m trying to put it to reality in my app. Maybe I don’t understand something, but if I try to use it as described in the article I get strange type incompatibility. Am I using something? Below I post simple use case.

package existential;

trait Loggable {
def log
}

class LoggableClass extends Loggable {
def log = print(“I’m being logged”)
}

object Existential extends Application {

def displayLoggableMap(
map: Map[
Loggable
, Loggable]) = {}

def displayLoggableMap2(
map: Map[
T forSome { type T <: Loggable }
, Loggable]) = {}

def displayLoggableMap3(
map: Map[
T forSome { type T <: Loggable }
, T forSome { type T <: Loggable }]) = {}

val map = Map(new LoggableClass -> new LoggableClass)

displayLoggableMap(map) // type mismatch
displayLoggableMap2(map) // type mismatch
displayLoggableMap3(map) // type mismatch
}

3. David R. MacIver

Hi,

What you want your argument to be is probably a Map[T, T] forSome { type T <: Loggable }

You might want to reread what I wrote about T forSome { type T}. T forSome { type T <: Loggable } is the same as Loggable. So your different method signatures were really all just Map[Loggable, Loggable].

4. Mateusz

I admit the paragraph is little unclear for me. Now I created

def displayLoggableMap4(
map: Map[T,T] forSome { type T <: Loggable }) = {}

and it compiles fine. However I can swear it didn’t work when I tried first time, before posting. Maybe it was another error. Once again thanks and I’ll try to understand it once again :).

5. Germán

Nice post. The notation seems too verbose for Scala…

In case mateusz wished to support maps with key/value that aren’t necessarily the same type (though both extending Loggable), this is probably what he/she should do:

def displayLoggableMap3(map:Map[T,U] forSome {type T<:Loggable; type U<:Loggable}) = ()

6. martin

> Nice post. The notation seems too verbose for Scala…

… which is intentional. We do not recommend you use existential types unless you have to, for instance because you interact with Java wildcards. Normally, abstract type members are preferrable.

7. Germán

Martin,
Assuming the Loggable example doesn’t require interaction with Java wildcards, what would the displayLoggableMap function look like avoiding this notation? Should it be defined in a class/object with a type T <: Loggable ?
Thanks

8. martin

German,

Yes, I would try an abstract type.
I have not looked at the example in
detail though.

9. Christopher

It has been a while since your post. Using Scala 2.9 I cannot confirm your point. Maybe it changed since 2.7. In 2.9 List[Class[_]] seems to be identical to List[Class[T] forSome{type T}] (and not to List[Class[T]] forSome{type T} as you say).

var l : List[Class[_]] = List(classOf[Int],classOf[String]) # works fine
var l : List[Class[_]] = List(classOf[String],classOf[String]) # works fine
var l : List[Class[_]] = List(classOf[Any],classOf[Any]) # works fine

var l : List[Class[T forSome{type T}]] = List(classOf[Int],classOf[String]) # type error
var l : List[Class[T forSome{type T}]] = List(classOf[String],classOf[String]) # type error
var l : List[Class[T forSome{type T}]] = List(classOf[Any],classOf[Any]) # works fine

var l : List[Class[T] forSome{type T}] = List(classOf[Int],classOf[String]) # works fine
var l : List[Class[T] forSome{type T}] = List(classOf[String],classOf[String]) # works fine
var l : List[Class[T] forSome{type T}] = List(classOf[Any],classOf[Any]) # works fine

var l : List[Class[T]] forSome{type T} = List(classOf[Int],classOf[String]) # type error
var l : List[Class[T]] forSome{type T} = List(classOf[String],classOf[String]) # works fine
var l : List[Class[T]] forSome{type T} = List(classOf[Any],classOf[Any]) # works fine

10. gunja

very confusing concept explained really nicely. atlast i understand them now.

Thanks a ton!!

11. Pingback: Scala Snippets « Stray Thoughts

12. Pingback: Scala教程：类型基础 - Noblog其他 | Noblog