Sunday, April 29, 2007

Of comonads and nightclubs

In this awesome explanation of monads, you have been building space stations under the master directive that all stations must output their astronauts in space suits. We're going to build nightclubs. In winter. Under the master directive that clients must take off their wintercoats before dancing.

We are especially concerned about the entrance procedure. There is a sequence of things which clients need to perform before they are allowed in. Maybe it's a private nightclub and you need to authenticate yourself. Maybe it's a high profile nightclub and you need to leave your limo keys to the valet. Maybe it's a paranoid nightclub and you need to be inspected for weapons. At one place I've been if you arrive early enough, they give you two empty glasses when you enter, and during the course of the night you can order exactly two free drinks. Maybe it's a rave and you need to buy enough drugs to scare sleep away for the entire night. Maybe there's a cover fee, and maybe it's lady's night so a girl's entrance procedure will be different from a guy's. And most importantly, you need to check your wintercoat at the coat check.

Now imagine you are working for a nightclub entrepreneur who had so much success so far that he plans to build a whole slew of different kinds of nightclubs. In consequence of his first success, he considers himself an expert of dancing floor design; he won't let you play near those. Nightclub entrances, on the other hand, they're all yours.

At the Entrance Parts Supermarket, you discover that entrances are made out of modular parts. There is a cover fee part, a parking part (valet not included), and even a case of part which can distinguish between guys and girls. There are pre-assembled kits, for common combinations such as a counter for both the cover fee and the coat check.

Your boss doesn't really understand the point of modular design. He insists that he will only pay for parts which make sure that clients check out their wintercoats. No amount of argumentation will convince him that a single nightclub entrance will only ever need a single coat check module, and that it's okay for the other modules not to repeat the same job. So you end up buying a bunch of reusable entrance parts which you can't even compose since once free of their wintercoats, clients won't be able to go through further wintercoat-removing steps.

Okay, so what did you do in the spacesuit example when you ended up with a whole bunch of incompatible space stations? You built a bind robot to extract the astronaut out of his spacesuit, feeding the astronaut into the next space station. Our bind robot will do exactly the opposite: in so far as a spacesuit can be thought of as a really expansive and overkill wintercoat, our bind robot (=>>) will put a client back into a suit, feeding the suited client into the next entrance part.

This system allows us to use any ordinary modular entrance part, provided it is available as a pre-assembled kit with a coat check included. It also allows us to use those fancy new parts which don't need to be grafted with coat checks, because taking clients out of their coats is part of their raison d'ĂȘtre. For instance, crooked nightclubs might want to use the all-in-one cover fee + coat check counter not as a pre-assembled kit, but as a simple coat check counter with crooks hired to steal any valuables from the coats. A nightclub featuring a lady's night might want to avoid the embarrassment of having to ask a "borderline" client what his/her gender is. Because of the (ridiculous) convention of placing a coat's zipper handle on one side for girl coats and on the other side for guys, a special coat check counter could provide a heuristic. At a beach-themed nightclub, clients could be required to put on swimwear, and it would make sense to provide lockers for clients to store both their street clothes and their wintercoats.

Monads were kinds of spaces, and different monads required different kinds of spacesuits with different procedures for astronauts to take them on and off. Some special space stations had a built-in ability to put astronauts into suits. A monad-specific robot named "bind" allowed ordinary and special space stations to intermingle. That was the whole point of monads: a framework to elegantly integrate special functions with the rest of our computation.

Comonads are kinds of snow, and different comonads require different kinds of wintercoats with different procedures for clients to take them on and off. Some special entrance parts have a built-in ability to take clients out of their wintercoats. A comonad-specific robot named "bind" allows ordinary and special entrance parts to intermingle. That is the whole point of comonads: a framework to elegantly integrate special functions with the rest of our computation.

Both monads and comonads are needed because they handle different categories of special functions. And bimonads, actually called arrows, can handle either kind, as well as brand new special functions which no monad nor comonad has ever dreamt of...

Saturday, April 28, 2007

I understand comonads

Upon discovering the incredible coolness of monads, I decided that the closely related concept of comonads had to be at least as interesting. Unfortunately, far fewer people seem to be interested in this little underestimated cousin, at least not enough for anyone to post a spacesuit metaphor for them. But as always, when proper documentation is lacking, it suffices to ask the source.

haskell class Monad m where haskell (>>=) :: m a -> (a -> m b) -> m b haskell return :: a -> m a haskell haskell class Comonad w where haskell (=>>) :: w a -> (w a -> b) -> w b haskell extract :: w a -> a

Okay, so this time the source didn't help much, since there are just types and no code. That's because monads and comonads are abstract classes (although Haskell probably uses a different terminology), whose implementation details are left to subclasses.

Yet types alone can say a lot. If I gave you a mysterious function whose type was (a -> a) and which worked for any possible type a, it would be pretty clear that I gave you the identity function. If I gave you a mysterious function whose type was (a -> (a -> b) -> b) and which worked for any possible types a and b, it would be pretty clear that I gave you a function which applies its second argument to the first. And that's exactly the kind of behaviours which the mysterious return, extract, (>>=), and (=>>) must exhibit, except they must deal with the extra m and w stuff as well.

Let's pause to ponder the apparent futility of a function which applies its second argument to the first. It is exactly like function application, but its arguments are in the opposite order. Why would anyone work backwards like this? Many people, in fact.

python abs(int("-42")) ruby "-42".to_i.abs

So "binding a value to a function" is just functional-programming jargon for the standard object-oriented way of chaining computations together. What is incredible with monads and comonads is that each different m and w provides a slightly different behaviour for this dot operator. Who knew we could need more than one?

A concrete monad or comonad implementation of a binding arrow, thus, simply applies its second argument to the first, and deals with the extra m or w stuff as well. Monad and comonad users must also deal with the extra m and w stuff, because they are the ones writing the (a -> m b) and (w a -> b) functions which (>>=) and (=>>) expect. Fortunately for them, return and extract can be used to lift their ordinary (a -> b) functions into a suitable form.

haskell lift_m :: Monad m => (a -> b) -> (a -> m b) haskell lift_m f a = return (f a) haskell haskell lift_w :: Comonad w => (a -> b) -> (w a -> b) haskell lift_w f a = f (extract a)

The big difference between using monads, comonads, or the ordinary dot operator is the kind of non-lifted functions which can be used. For the ordinary dot operator there are none, for monads there are functions which can stuff something extra along the return value, and for comonads there are functions which can extract something extra out of the input value.

A spacesuit example should follow soon.