Covariant, Contravariant and Invariant Types

Now let’s talk about an error you might get from a compiler that can be confusing at first, but it makes sense once you think about it. (That’s usually how it is with compile errors, right?) Question:

If I have a function that takes a List<Animal> as argument, should I be able to pass it a List<Cat>?

Uh, that depends on the programming language, as it turns out – but let’s think about it in the spirit of Barbara Liskov’s “substitution principle:” if something has to be an Animal and it turns out it’s actually a Cat, that should be fine almost by definition: instances of the subclass are acceptable where the superclass is expected. Cat is a subclass of Animal, so if there’s a function that wants an Animal, I can give it a Cat and that’s fine. So far so good.

But back to the question: should List<Cat> be a subclass of List<Animal>? You might think “yes?” because the function should be fine, right? It’s going to do stuff with this list, it expects there to be animals, and: there are. In fact they’re all cats, but who cares. What could go wrong?

Well I’ll tell you what’s going to go wrong, the function is going to insert a Dog! As far as it knows, this is a List<Animal>; dog is an animal, so it can go in the list. But now if this list was passed by reference, that’s a problem: the caller now has a dog in (what they think is) a list of cats. Surely that should be a type error; if not at compile time, then at runtime.

So Java, for example, says no: List<Cat> is not a subclass of List<Animal>. Making the call suggested above is a static type error. (It’s different for Java arrays, incidentally: the call is allowed, but it’s a runtime error to insert a dog.) So conceptually, lists – in a pass-by-reference language that wants static type safety – are what’s called “invariant” to their element type. List<A> has no subclass relationship to List<B>, even if there is one between A and B.

If the list is passed by value, or let’s say as a read-only iterator, then my original intuition was right: ReadOnlyInterator<Cat> can indeed safely substitute for a ReadOnlyIterator<Animal>. This is called covariance: you inherit (no pun intended) the subclass relationship of your type variable.

Interestingly, there are also natural examples of contra-variant types. Consider Animal -> String and Cat -> String. Think about it: if you want a function from Cat to string, in terms of the substitution principle it’s actually fine if I give you a function from Animal to string – that works just fine. This is contravariance, which flips the subclass relation: Animal -> String should be a subclass of Cat -> String!

So if you ever run into a compile error surrounding this, you can remember this post and not be confused, and hopefully it helps you think about these concepts a little bit more clearly; it’s also in this context that Java ends up with that seemingly silly <? extends T> syntax, but you can look up on your own why that helps.