Tuesday, January 14, 2014

Functors are computations

Review: Functors are containers


Bartosz Milewski wrote a controversial (at the time of writing, 8 votes up and 8 votes down) post about Functors. The community really doesn't seem to like simplistic analogies such as "Functors are containers", "Monads are computation", or "Comonads are neighbourhoods".

Personally, I find those analogies very useful, as long as you know exactly which parts of the analogy apply. I think what the community doesn't like about analogies such as "Functors are containers" is that they are misleading. And if you only say that, "Functors are containers", then it is indeed misleading. You think you know what a container is (a plastic box in which I can put food?), and now you think you also know what a Functor is (a crazy math name for a plastic container?), but of course that's not what the analogy is trying to say. Stating the analogy is only the first step; we give your intuition a place to start, something familiar, and now we need to explain exactly how much Functors are like containers, and in which ways they are not like containers (i.e. they are not made of plastic). Let's do this now:

Functors are containers, but not the kind of containers you can put stuff inside and then take your stuff out. They are only containers insofar as a Functor f a may contain zero or more values of type a, they are in there somewhere even if you might not be able to see them. Oh and also there is a function fmap which allows you to uniformly modify all the a values inside the container. And also if you use fmap with a function of type a → b, which changes the type of the a values to b, then obviously all the values now have type b, so you have now converted your f a container into an f b container, which contains b values instead of a.

A less convoluted but more mathematical way of saying the above is to say that a Functor is any type constructor f :: * → * such that there exists a function fmap of type (a → b) → f a → f b. This is what the community likes to hear. But I don't like that version; it is dry, there is no intuition, and it doesn't give me the gut feeling that I truly understand Functors.

New stuff: Functors are also computations


Careful there. Yes, starting from containers allows me to feel like I truly understand functors, but if I really do understand them, then I should be able to recognize them even when they are being presented under a different disguise. Here is one: Functors are (also) computations.

Functors are computations, but not the kind of computation you can run in order to obtain a result, nor even the kind of computation which you can compose into a longer computation if you run two of them one after another. Functors are only computations insofar as a Functor f a may compute a value of type a, somehow, even if you might not be able to retrieve it. Oh, and there is a function fmap which allows you to add some post-processing after the computation by modifying the result. And if the post-processing is a function of type a → b, which changes the type of the intermediate a result to a final result of type b, then obviously the overall computation is now producing a value of type b, so you have now converted your f a computation into an f b computation, which produces a b instead of an a.

The same goes for Applicative, Monad, etc: they are containers, and they are also computations. Yes, you read that right, "Functors are containers" and "Applicatives are containers" and "Monads are containers". And computations. Of course they are not all containers in the same way; in each case, it is a different part of the analogy which is important, and you can only claim to understand the analogy if you understand which part that is. Your turn now, try it with a Monad: can you visualize both interpretations? If a Monad is a container, which parts make the container monadic? And if a Monad is a computation, which parts of the computation makes the computation monadic? Can you see how those parts are similar, maybe even two views of the same thing?

Bonus: The duality between containers and computations


Even though type theory already formally corresponds to many things, I haven't yet seen it explicitly stated anywhere, so remember that you saw it here first: containers and computations are dual to each other. Probably.

The fun part about dualities isn't proving that they are formally correct, so I won't bother to do that here. I think the fun part of dualities is trying to find what corresponds to what, by examining elements on one side of the duality and focussing on those for which your brain doesn't immediately bring up a twin from the other side. For example, I just said that Functors are computations to which you can add post-processing steps. Well, that raises the question: is there a kind of computation to which you can add pre-processing steps? Let's see, that would be some kind of antifmap taking a pre-processing function of type a → b and applying it before the input of the computation, thereby creating a computation with a different input type, a instead of b. Okay, so it looks like our computation f a is parameterized by its input type a. Then antifmap must have type (a → b) → f b → f a. Hey, that's a contravariant functor, what a pleasant surprise!

One last step, harder this time. What is the container interpretation of a contravariant functor? Try to figure it out. It's tricky, but you can do it!

Spoilers!


Gave up already? Here is a hint: think of a violin case. Is it still a violin case when you remove the violin? Why? Aha, now you're thinking with containers!