What is a contravariant functor?

Question

The type blows my mind:

class Contravariant (f :: * -> *) where   contramap :: (a -> b) -> f b -> f a 

Then I read this, but contrary to the title, I wasn't any more enlightened.

Can someone please give an explanation of what a contravariant functor is and some examples?

Answer 1

From a programmer's point of view the essence of functor-ness is being able to easily adapt things. What I mean by "adapt" here is that if I have an f a and I need an f b, I'd like an adaptor that will fit my f a in my f b-shaped hole.

It seems intuitive that if I can turn an a into a b, that I might be able to turn a f a into an f b. And indeed that's the pattern that Haskell's Functor class embodies; if I supply an a -> b function then fmap lets me adapt f a things into f b things, without worrying about whatever f involves.¹

Of course talking about paramterised types like list-of-x [x], Maybe y, or IO z here, and the thing we get to change with our adaptors is the x, y, or z in those. If we want the flexibility to get an adaptor from any possible function a -> b then of course the thing we're adapting has to be equally applicable to any possible type.

What is less intuitive (at first) is that there are some types which can be adapted almost exactly the same way as functory ones, only they're "backwards"; for these if we want to adapt an f a to fill a need for a f b we actually need to supply a b -> a function, not an a -> b one!

My favourite concrete example is actually the function type a -> r (a for argument, r for result); all of this abstract nonsense makes perfect sense when applied to functions (and if you've done any substantial programming you've almost certainly used these concepts without knowing the terminology or how widely-applicable they are), and the two notions are so obviously dual to each other in this context.

It's fairly well known that a -> r is a functor in r. This makes sense; if I've got an a -> r and I need an a -> s, then I could use an r -> s function to adapt my original function simply by post-processing the result.²

If, on the other hand, I have an a -> r function and what I need is a b -> r, then again it's clear that I can address my need by pre-processing arguments before passing them to the original function. But what do I pre-process them with? The original function is a black box; no matter what I do it's always expecting a inputs. So I need to turn my b values into the a values it expects: my pre-processing adaptor needs a b -> a function.

What we've just seen is that the function type a -> r is a covariant functor in r, and a contravariant functor in a. I think of this as saying we can adapt a function's result, and the result type "changes with" the adaptor r -> s, while when we adapt a function's argument the argument type changes "in the opposite direction" to the adaptor.

Interestingly, the implementation of the function-result fmap and the function-argument contramap are almost exactly the same thing: just function composition (the . operator)! The only difference is on which side you compose the adaptor function:³

fmap :: (r -> s) -> (a -> r) -> (a -> s) fmap adaptor f = adaptor . f fmap adaptor = (adaptor .) fmap = (.)  contramap' :: (b -> a) -> (a -> r) -> (b -> r) contramap' adaptor f = f . adaptor contramap' adaptor = (. adaptor) contramap' = flip (.) 

I consider the second definition from each block the most insightful; (covariantly) mapping over a function's result is composition on the left (post-composition if we want to take a "this-happens-after-that" view), while contravariantly mapping over a function's argument is composition on the right (pre-composition).

This intuition generalises pretty well; if an f x structure can give us values of type x (just like an a -> r function gives us r values, at least potentially), it might be a covariant Functor in x, and we could use an x -> y function to adapt it into being an f y. But if an f x structure receives values of type x from us (again, like an a -> r function's argument of type a), then it might be a Contravariant functor and we'd need to use a y -> x function to adapt it to being an f y.

I find it interesting to reflect that this "sources are covariant, destinations are contravariant" intuition reverses when you're thinking from the perspective of an implementer of the source/destination rather than a caller. If I'm trying to implement an f x that receives x values I can "adapt my own interface" so I get to work with y values instead (while still presenting the "receives x values" interface to my callers) by using an x -> y function. Usually we don't think this way around; even as the implementer of the f x I think about adapting the things I'm calling rather than "adapting my caller's interface to me". But it's another perspective you can take.

The only semi-real-world use I've made of Contravariant (as opposed to implicitly using the contravariance of functions in their arguments by using composition-on-the-right, which is very common) was for a type Serialiser a that could serialise x values. Serialiser had to be a Contravariant rather than a Functor; given I can serialise Foos, I can also serialise Bars if I can Bar -> Foo.⁴ But when you realise that Serialiser a is basically a -> ByteString it becomes obvious; I'm just repeating a special case of the a -> r example.

In pure functional programming, there's not very much use in having something that "receives values" without it also giving something back so all the contravariant functors tend to look like functions, but nearly any straightforward data structure that can contain values of an arbitrary type will be a covariant functor in that type parameter. This is why Functor stole the good name early and is used all over the place (well, that and that Functor was recognised as a fundamental part of Monad, which was already in wide use before Functor was defined as a class in Haskell).

In imperative OO I believe contravariant functors may be significantly more common (but not abstracted over with a unified framework like Contravariant), although it's also very easy to have mutability and side effects mean that a parameterised type just couldn't be a functor at all (commonly: your standard container of a that is both readable and writable is both an emitter and a sink of a, and rather than meaning it's both covariant and contravariant it turns out that means it's neither).

---

¹ The Functor instance of each individual f says how to apply arbitrary functions to the particular form of that f, without worrying about the particular types f is being applied to; a nice separation of concerns.

² This functor is also a monad, equivalent to the Reader monad. I'm not going to go beyond functors in detail here, but given the rest of my post an obvious question would be "is the a -> r type also some sort of contravariant monad in a then?". Contravariance doesn't apply to monads unfortunately (see Are there contravariant monads?), but there is a contravariant analogue of Applicative: https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant-Divisible.html

³ Note that my contramap' here doesn't match the actual contramap from Contravariant as implemented in Haskell; you can't make a -> r an actual instance of Contravariant in Haskell code simply because the a is not the last type paramter of (->). Conceptually it works perfectly well, and you can always use a newtype wrapper to swap the type parameters and make that an instance (the contravariant defines the the Op type for exactly this purpose).

⁴ At least for a definition of "serialise" that doesn't necessarily include being able to reconstruct the Bar later, since it would serialise the a Bar identically to the Foo it mapped to with no way to include any information about what the mapping was.