Covariance and Contravariance with Horses and People

Recently, some people on one of the scala mailing lists got into the usual discussion on covariance and contravariance, when Kris Nuttycombe [Ext. Link]correctly remarked that the best illustration for the meaning of variance is the trait Function1[-A,+B], which shows both types of variance in a single, simple package. But still, someone else wanted pictures.

It didn't take long for somebody to take up the challenge, but the resulting set of diagrams was quickly criticized for lacking [Ext. Link]'horses (or ponies), ducks, house, beaches, trees, cars people or anything like it'. So here it is: Co- and Contravariane in Function1[-A,+B] with horses and people.

In scala, the notation Function1[A,B] says that Function1 is a type parametrized over two arbitrary other types called A and B, and its meaning is that of a function from arguments of type A to values of type B. For this discussion, it is the easiest to interpret a type as the set of values belonging to that type. In the following picture, the type A is a set of horses, the type B is a set of people, and the arrows describe a function of type Function1[A,B].

[A function from a set of horses to a set of people]

But the full type of Function1[-A,+B] contains these funny little signs that denote the variance, the minus meaning that it is contravariant in A, the plus meaning that it is covariant in B. The variance tells me that I can use this function with a more flexible type than plain Function1[A,B], I can use it with any type Function1[X,Y] where X is a subset of A and Y is a superset of B. "Using with this type" here means that I call this function in a context where I know (or, rather, the compiler can prove) that the argument passed to the function is always a member of the set X, and the code handling the result of the function can process any value that is a member of set Y. This is illustrated in the following picture:

[A function from a subset of the horses to a superset of the people]

It doesn't hurt at all if I restrict the function to just the brown horses, it will always return a well defined person for that horse. But it would fail if I called it with a cow.

On the other hand, if it perfectly OK if I use the function to see which people of a larger group that does even include people with hats get a horse. A lower percentage of those people than of the original set will get a horse, which may be frustating for them, but is still correct. Life isn't fair. But if I used the function on the given horses in a context that can't handle girls, things would go amiss.

But what about the funny names?

The first type paramter of Function1 is called contravariant, because the relation between sets of functions goes against the relation between the sets of values they accept: A function that accepts elements of a superset of the set of brown horses is among other thing a function that accepts brown horses, so the set of functions accepting supersets of the set of brown horses is a subset of the set of functions that accept brown horses.

The second type parameter of Function1, the type of the return values, is called covariant because the relation between sets of functions is the same (goes with) the relation between the sets of their return types. A function that may return elements of a superset of the persons without hat is not an element of the set of functions that return persons without hats (or, at least, not statically known to be so). It is only an element of a larger set of functions. But a function that only returns elements of a subset of the persons without hats (say, girls without hats) is a function that returns persons without hats, so the set of the functions returning a subset of the persons without hats is a subset of the set of functions returning persons without hats.


Of course, this page gives a concrete example of an abstract mathematical concept. If you really wanted to understand the concept, you [Ext. Link]shouldn't have read this page.

Florian Hars <>, 2010-11-09 (orig: 2009-10-31)