(Updated on Aug 22, 2014, better title, add link)

Intro

Let's go beyond monad, today I want to show you how to play with comonad. I don't understand the theory behind comonad, but programming with it is quite simple. Basically, I think it's just an algebraic structure dealing with data context.

In other words, if you find yourself dealing with some recursive data structure, and in that data structure, the value of one place depends on the value of its neighborhoods (some “data context”, not sure if I'm using the right terminology), you probably want to take a look at comonad.

Conway's Game of Life

To do something interesting with comonad, the first thing came to my mind was Game of Life. It's a simple “game” that involves no players. At the beginning, a world is represented as a 2D array of booleans. Then this world evolves following some simple rules.

Looking at these rules, you will find that the next state of a given cell in the world is merely determined by the previous states of itself and its neighborhoods. So I feel Game of Life would be a perfect example for comonad.

Comonad

Recall what is a monad in Haskell code:

class Functor m => Monad m where
    return :: a -> m a
    join   :: m (m a) -> m a

I lied here because to define a Monad, Haskell does not require you to make it an instance of Functor at the first place. But trust me this requirement will be forced in future.

In addition, I don't define a (>>=) but instead a join, since f >>= m = join (fmap f m), and m should also be an instance of Functor, this monad definition should be almost equivalent to the one found in the base library.

Whenever we “co-” something, it means to filp every -> into <-. So we know what a comonad would look like:

class Functor w => Comonad w where
    extract   :: w a -> a
    duplicate :: w a -> w (w a)

    extend    :: (w a -> b) -> w a -> w b
    (=>>)     :: w a -> (w a -> b) -> w b

Here you can see we flip the type signature for return and join, we get extract and duplicate as results. It's also handy to have extend and (=>>), which can all be defined in terms of fmap and duplicate, just like (=<<) and (>>=) functions for monad. Let's try to figure out the implementation of extend.

The first step is to bind the arguments of extend to some name (here f and w1), so we can list all the tools available:

extract    :: forall a   . w a -> a
duplicate  :: forall a   . w a -> w (w a)
fmap       :: forall a b . (a -> b) -> w a -> w b
f          :: w a -> b
w1         :: w a
-- goal:
extend f w :: w b

It's tempting to try f w1 :: b, but it is a dead end. Instead, because f “removes a layer of w”, we can try to add another layer before using f:

duplicate w1          :: w (w a)
fmap                  :: (a' -> b') -> w a' -> w b'
-- where a' = w a, b' = b
fmap f (duplicate w1) :: w b

Therefore:

extend f w = fmap f (duplicate w)
w =>> f    = extend f w

or more point-freely:

extend f = fmap f . duplicate
(=>>)    = flip extend

Some understanding about comonad

In my opinion, when trying to understand monad, it's more straightforward to begin with understanding fmap, return and join, but in practice, >>= and =<< come in handy. And the same thing happens to comonad: extract and duplicate are easy, and extend and =>> come in handy.

Recall that in the intro section, I said comonad deals with data context. More precisely, (IMHO) it's a type constructor that adds to a data structure the ability of focusing on one particular value and the ability of moving focus.

• extract means to extract a value from the current focus, this can be seen from its type signature extract :: w a -> a.
• duplicate might not be that straightforward to understand. It means to replace every value in the data structure, with its corresponding context.

To make an analogy, assume you are inside of a big building, there are maps indicating the spot you are currently standing. If this building were a comonad, and the focus was on you. I can use extract to directly find you. In addition, there are some places with maps. These maps provides you with not only the whole structure of this building, but also the place where every map itself is located. So if you are inside a building near a map, you can take a picture on the map and send it to me, then I can locate you using extract.

Now suppose there is a building without maps, what duplicate does is just like drawing maps for each place inside the building and putting them to their right places. So w is the building “comonad”, a is a single place inside the building and duplicate :: w a -> w (w a) draws maps and put them to their corresponding places.

And just like (>>=) in monad, (=>>) is more handy to use in comonad. Looking at its signature (=>>) :: (w a -> b) -> w a -> w b, the most interesting part is its first argument, a function of type w a -> b. This argument is exactly where rules come into play: “Given a data with focus (w a), let's determine the next value of the current focus will be (b).”

I'd like to call it a day here. In the future posts, we'll see these functions in action.

Other parts

• Part 2