I heard the terms “covariance” and “contravariance” used in math long before I heard them used in object oriented programming. I was curious whether there was any connection between the two. To my surprise, they’re very similar. In fact, you could formalize the OOP use of the terms so that they’re not just analogous but actually special cases of the mathematical terms.
When I started writing this post, I intended to explain covariance and contravariance. However, the post became longer and more technical than I like to write here. Instead, I’ll just announce that a connection exists and give references for those who want to read further.
Chris Burrows describes covariance and contravariance in object oriented programming in his article New C# Features in the .NET Framework 4.
The terms covariant and contravariant were defined in category theory before computer scientists applied the terms to object oriented programming. Wikipedia has a short, readable introduction to category theory, including covariant and contravariant functors. See also A Categorical Manifesto (PostScript file).
Computer scientists have been interested in category theory for some time, so it’s not too surprising that category theory terms would filter down into practical programming. The real surprise was hearing category terminology used outside of math. It was like the feeling you get when you run into a coworker at a family reunion or a neighbor at a restaurant in another city.
Update (3 Jan 2011): See also Liskov Substitution Principle is Contravariance
Update (28 Feb 2013): See also how covariance and contravariance are used in the opposite sense with vector fields.
5 thoughts on “Covariance and contravariance in math and CS”
Sorry, I cannot see the equivalence between category-theorethical and OO terms here. Maybe because I do not appreciate category theory? In math it seems to be a mapping replacing the domain and range of a functor, in OO it extends the range. Am I mistaken?
Marek: In OO, the mapping between base types induces a map between the corresponding parameterized types. In Chris Burrows’ article, his example is that a manager is a type of employee. This induces a relationship between iterators over managers and iterators over employees. The key observation is that the “arrows” in Burrows’ diagram go in the same direction.
Manager → Employee
IEnumerable<Manager> → IEnumerable<Employee>
This is covariance. And in his example of the IComparer interfaces, the arrows go the other way. This is contravariance.
Category theory looks at this kind of situation in general, when maps between objects induce maps between associated objects. The first example I saw was in algebraic topology. There you associate an algebraic object with a topological space with the hope that some questions about topology can be answered by answering questions about their associated algebraic structures. A continuous function between topological spaces induces a map between the associated fundamental groups. And the arrows go in the same direction: you have a covariant functor.
Category theory abstracts all this. It doesn’t care whether your objects are topological spaces or employees. The pattern is the same, and all it cares about is the patterns.
In Chris Burrows’ article, you could think of the map between Manager objects and Employee objects as extending the domain. But that could be misleading because the relationships category theory are concerned with are far more general. What matters is that there’s some mapping. In this case it’s such a simple mapping that it could be missed. You could have instead a more complex mapping, such as a map between the XML serialization of an object and its binary representation in memory.
I learned a long time about the Liskov Substitution Principle, which is closely related to Bertran Meyer’s “Design by Contract”, at least as the latter behaves under inheritance (i.e., covariant vs. contravariant behaviors). Recently, this post argued that the Liskov Substitution Principle is contravariance.
Looking forward to when you do clean up and do another post about co- and contra-variance. This is what’s on my desk to read about it.
I get the turning around arrows part (or I think I get it), but there also seems to be a relationship to raising and lowering indices in GR. Maybe I just don’t understand GR well enough and that’s the real problem.
Following is one of several good quotes from Chris Tiee about covariance and contravariance. The PDF is down (although I might post it drop.io if I feel adventurous) … hopefully Chris wasn’t taking that page down on purpose.
Think about a vector field. Do you want to take the derivative (x+h) – x of the TAILS of the vectors, or the HEADS?
Chris also makes the point that covariant and contravariant are mis-named, essentially because the people who invented the terms were thinking too much in terms of Calculation and not enough in terms of Geometry.