Monday, January 28, 2008

Existential types

Java generics haven't been fully supported in Scala until now. They're not in the newest official release, but you can already use them checking out them from the SVN or downloading a nightly build. To get Java generic interoperatibility working, Scala has gotten a new feature, existential types.

Existential types are in form of T forSome {type Q}, where Q part contains type declarations. In practice we want to just say some restrictions for T.

E.g. def m(x : t forSome {type t <: A}) = x is a method that takes arguments that conform to t <: A. You can read more specific info from the Scala specification.

One interesting thing about existentials is that you can use them to use-site variance when it's not possible to make the type covariant. Let's see what that means.
  • class Couple[a](val first: a, val second: a)
  • trait Creature
  • trait Human extends Creature
So we have a Couple class which has one type parameter, but two arguments of the same type. We also have some kind of hierarchy of traits which we use as type arguments to make a couple of type Couple[Human]:
  • val couple = new Couple(new Human{}, new Human{})
Now, without changes to Couple, we cannot pass couple to a function, which takes Couple[Creature] as argument, because Couple is invariant. I.e. S = T iff Couple[S] = Couple[T] holds. We need covariance to achieve that. I.e. S <= T iff Couple[S] <= Couple[T]. We could make Couple covariant in definition site by:
  • class Couple[+a](...)
... and then we could pass couple to a function like:
  • def haveFun1(c: Couple[Creature]) = c
  • haveFun1(couple) // compiles only if Couple is covariant in its type parameter
But we can do this without making changes to Couple definition, which could be impossible in some cases, or just not preferable. With the following definition we get what we want:
  • def haveFun2(c: Couple[x] forSome {type x <: Creature}) = c
  • haveFun2(couple) // compiles
There's a nicer syntax alternative (haveFun2 == haveFun3):
  • def haveFun3(c: Couple[_ <: Creature]) = c
This shows how existentials allow the treatment of a Human Couple as a Creature Couple in the client code.

If you want to read more about the usefulness of existentials, see Burak Emir's interesting article how they relate to pattern matching here.

1 comment:

Henrik Huttunen said...

I just noticed that David MacIver has written very similar blog post.

Link