This post originated from an RSS feed registered with Java Buzz
by Mathias Bogaert.

Original Post: Covariance and Contravariance in Scala
Feed Title: Scuttlebutt
Feed URL: http://feeds.feedburner.com/AtlassianDeveloperBlog
Feed Description: tech gossip by mathias

I spent some time trying to figure out co- and contra-variance in Scala, and it turns out to be both interesting enough to be worth blogging about, and subtle enough that doing so will test my understanding! So, you’ve probably seen classes in Scala that look a bit like this: 12345sealed abstract class List[+A] { def head : A def ::[B >: A] (x:B) : List[B] = ... ... } And you’ve probably heard that the +A means that A is a “covariant type parameter”, whatever that means. And if you’ve tried to use classes with co- or contra-variant type parameters, you’ve probably run into cryptic errors about “covariant positions” and other such gibberish. Hopefully, by the end of this post, you’ll have some idea what that all means. The first thing that’s going on there is that List is a “generic” type. That is, you can have lots of List types. You can have List[Int], and List[MyClass] or whatever. To put this in another way, List[_] is a type constructor; it’s like a function that takes another concrete type and produces a new one. So if you already have a type X, you can use the List type constructor to make a new type, List[X]. A little bit of category theory To get the cool stuff in all its generality, we’re going to need to start thinking about things in terms of categories. Fortunately, it’s pretty non-scary categories stuff. Recall that a category C is just some objects and some arrows (which we usually gloss as “functions”). Arrows go from one object to another, and the only requirements for being a category are that you have some binary operation on arrows (usually glossed as “composition”), that makes new arrows that go from and to the right places; and that you have an “identity” arrow on every object that does just what you’d expect.1 The category we’re mostly interested in is the category of types: types like Int, Person, Map[Foo, Bar] are the objects, and arrows are precisely functions. The other concept we’re going to need is that of a functor. A functor F: C -> D is a mapping between categories. However, there’s no reason you can’t have functors from categories to themselves (“helpfully” called “endofunctors”), and those are the ones we’re going to be interested in. Functors have to turn objects in the source category into objects in the target category, and they also have to turn arrows into new arrows. Again, functors have to obey certain laws, but don’t worry too much about that.2 Okay, so who cares about functors? The answer is that type constructors are basically functors on the category of types. How is that? Well, they turn types (which are our objects) into other types: check! But what about the arrows (i.e. functions). Don’t functors have to map those over as well? Yes, they do, but in Scala we don’t call the function that comes out of the List functor List[f], [...]