Tab Completion

I'm Tab Atkins Jr, and I wear many hats. I work for Google on the Chrome browser as a Web Standards Hacker. I'm also a member of the CSS Working Group, and am either a member or contributor to several other working groups in the W3C. You can contact me here.
Listing of All Posts

I Understand Contravariant Functors Better Now!

Last updated:

Regular readers probably know that I enjoy some functional programming from time to time, and occasionally like to dive into Haskell and related stuff to teach myself something new. One thing that I've seen several times now, but not understood until now, is the idea of a "contravariant functor" or "cofunctor", and more generally the idea of something being covariant or contravariant over a type argument.

These concepts come from math, and I only vaguely understand what Wikipedia is talking about when they describe them. Translating over to category theory just obscures things further; it's made more difficult by the fact that both Abstract Math Wikipedia and Category Theory Wikipedia have fetishes for symbol-heavy statements that they apparently think make things clearer.

But at least within practical programming, I have a grasp on it, and I'll attempt to explain it to you, the abstract Reader.

Review of Covariance

So a quick review of "normal" functors. Say you've got a function that takes an integer and returns it "spelled out"; numSpell(1) returns "one", etc. You want to call this on some integers you've got lying around, but alas, they're stored in an array and you don't know how many there are. Not to worry, Array is a functor, so you can call its map() method, passing numSpell to it, and you'll get back an Array of strings, having had numSpell applied to each of the integers inside the array.

In the abstraction of types, what happened is that you started with an Array<Int> and a function Int->String, and the map() function let you combine these two to get an Array<String>. That's a normal, covariant functor.

Broken Intuition

Now, a contravariant functor, or cofunctor (I'm so sorry, category theorists are just the absolute worst at terminology) is kinda similar, but different in a way that's very confusing at first.

While map() takes an F<A> functor and a A->B function, producing an F<B> functor, contramap() takes an F<A> cofunctor and an B->A function, and produces an F<B> cofunctor. That's... backwards??? How can you take an B->A function, and a thing of type A, and get an B out of it?

Turns out the problem is in our intuition, or at least, in my intuition. I'd gotten very used to thinking in terms of the "functor is a container" abstraction. That serves you well for many functors, like Array or Option, but it can lead you astray for more abstract functors. More importantly, tho, it led me to develop an intuition that the type parameter of a generic like, like Array<Int>, was telling me what sort of value was inside the object; Array<Int> is an Array containing Ints, after all.

But that's not it at all! The type param is just telling me that, in the methods for the object, some functions will have different type signatures depending on what I specify. For Array<Int>, it's telling me that array access, the arr[i] syntax, will produce an Int, whereas in Array<String> the exact same syntax will produce a String.

In this case, and in general for functors, the type parameter is always going to be dictating the return value of some methods on the object. In other words, the functor is a producer of some sort of value, and the type param tells me what type of value that will be.

With this minor insight, the fact that map() can use an A->B function to turn an F<A> into an F<B> makes sense; the F<A> will try to produce an A value normally, then you pass it thru the A->B function and get a B instead.

Contravariance

So then we can take that minor insight further: what happens when the type parameter is instead telling you an argument type for methods? That is, the object consumes values of that type?

For example, say you have a Serializer class, that converts things to bytes, for writing to files. It can take lots of different types of objects, so it's qualified as well: Serializer<Int>, Serializer<Bool>, etc.

So first, this can still be a functor (or technically, functor-adjacent) - it produces bytes, so you can .map() over those bytes to produce something else, by passing a Bytes->Whatever function.

But the type term, the Int or Bool or whatever, doesn't show up in that function, as it just handles Bytes. If you have a Serializer<Int>, you can't pass it the numSpell function, which is Int->String, and suddenly get a Serializer<String>, aka something which knows how to consume strings and output bytes. numSpell just doesn't help with that; it turns Ints into Strings, while our Serializer<String> is given Strings, and the Serializer<Int> it was based on only knows how to serialize Ints.

In order to transform a Serializer<Int> into a Serializer<String>, we obviously need a String->Int function. Pay attention there: with normal functors, turning F<A> into F<B> requires an A->B function. But turning Serializer<A> into Serializer<B> requires a B->A function. This makes perfect sense in concrete terms: your starting functor produces As, so an A->B function lets you transform that into a B so you can start producing Bs instead; but your Serializer consumes As, so you need a B->A function so you can start accepting Bs instead, transforming them into the As you already know how to deal with. This makes Serialize a contravariant functor, or cofunctor, and so it has a .contraMap() method instead, which takes the opposite-direction callback and uses it to transform itself.

Profunctors, Etc.

So that's the essence here. If a functor is covariant in one of its types, that means it is, in some sense, producing values of that type; they're return values for some method. If you want to transform it from F<Int> to F<String>, you need to provide an Int->String method to .map(). If a functor is contravariant in one of its types, it's the opposite: it consumes values of that type, taking them as arguments to some method. To transform it from F<Int> to F<String>, you need to provide a String->Int method to .contraMap().

There's a two-typed structure called a Profunctor that does both at once; a Profunctor<Int, String> is contravariant in Int and covariant in String. The classic example of a Profunctor is... a function, like numSpell from earlier. In general, functions are characterized by two type parameters, A->B; for numSpell, that's Int->String.

If you want to change an A->B function to a C->D function, you need to provide two transformations, something to change the type A to C, and something to change the type B to D. Since the function produces a B, you want to give a B->D mapping function so it can start producing Ds instead; since it consumes an A, you want to give a C->A contramapping function so it can start consuming Cs instead.

(a limited set of Markdown is supported)