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

Things That Aren't Other Things, Monad Edition

Last updated:

An intuitive example of something that's a Functor but not an Applicative is a tagged value, where you have a value that's associated with some arbitrary "tag". This is a functor - given a function f and a tagged value ("tag1", v), you can map over it to get the result ("tag1", f(v)). But it's not an applicative: for one, there's no "default" tag, so it's not Pointed, but also given ("tag1", f) and ("tag2", v), the result should have a value of f(v), but what would the tag be? There's no automatic way to generate a tag from two existing tags.

An intuitive example of something that's an Applicative (a Traversable, really) but not a Monad is a ZipList. Given [f1, f2] and [v1, v2, v3], you'll end up with [f1(v1), f2(v2)], so it's Applicative. But implementing join is impossible in general - given [[a1, a2], [b1], [c1, c2, c3]], the obvious way to collapse it into a single ziplist is to take the Nth element of the Nth list. But there's no b2 element! Fixed-length or infinite-length ziplists are Monads, though. (Why can't you just stop at the first one that fails, returning [a1]? It violates the monad laws! Usually associativity, depending on exactly what you implement.)

An intuitive example of something that's an Applicative but not a Traversable is IO. An IO is an Applicative - you can join an IO and an IO into an IO that just performs the side-effects of both source IOs in order. But the essential characteristic of a Traversable is that you can build an identical version of one just by looking at its internal values. A list is a Traversable - once you pull its values out, you can just put them in a new list in the same order, and the old and new are functionally indistinguishable. But the same isn't true of an IO - the internal value is the result of some operation which has side effects, and those side-effects aren't extractable or reproducible. If you try and make a new IO from an existing one, all that happens is you end up executing the side-effects once, and then the new one is a sterile IO with no side-effects at all.

Another example of Applicative-but-not-Traversable is Function, for similar reasons - the value "inside" of a Function is its return value. Its Applicative instance just holds onto the two source Functions; when you go to extract the value (by giving it an input argument), it feeds it to each of the source Functions, producing a function and a value, then calls the former on the latter and returns the result. But the code that transforms the input into the output is hidden internal state, which is not extractable, so you can't "rebuild" a function by extracting its return value; at best you can produce a constant function that just returns the same thing as the Function does for a single particular value.

Interesting side-note: the Writer monad is almost identical to the tagged value - it's conceptually a value paired with a "logging value". The difference is that the logging value is not arbitrary - it's required to be a monoid. This gives us a default value, so it's Pointed, and a way to combine logging values, so ("log1", f) and ("log2", v) can be combined into ("log1log2", f(v)). So Writer is Applicative, and in fact a full Monad.

(a limited set of Markdown is supported)