Notes on Comonads

This excellent post by Eli Jordan can be summarized as comonads offer counit and cojoin, the opposites of on unit and join (or flatten as Cats calls it) monads. 

Why this is useful is that it can model a use case where there is the notion of focus. To demonstrate this, Jordan has created an implementation of Conway's Game of Life (code). Here, the focus is a cell which we determine is either on or off given its neighbours. (Another example of how comonads use focus can be found here where we traverse a graph, node by node).

The case class on which we will call counit and cojoin is an abstraction, Store[S, A], but for the Game of Life example, it is the grid on which the changing cells live. Notably, Store is instantiated with two arguments, 

1. lookup: S => A
2. index: S  

Specifically for our game, these represent:

1. a mapping from a co-ordinate (S) to a Boolean (A) representing whether the corresponding cell is turned on or off.
2. the co-ordinates of the cell that has the focus. That is, S for us is of type (Int, Int).

For each step in our game, we ask our grid (Store) what the neighbourhood is like (lookup) for its focused cell (index). 

We do this by calling its Cats coflatMap function (that we added via a type class) that takes a grid and returns a Boolean. 

This is where it gets interesting. You'll notice that Store has the potential for a partially applied constructor. That is, it looks like:

case class Store[S, A](lookup: S => A)(val index: S) { ...

So, if we instantiate Store with just a S => A, we actually have a S => Store[S, A].

In our Game of Life, this means that for the coflatMap branch of the code, the grid is not actually a mapping to whether the cell is turned on or off (F[Boolean]) but to the grid of the previous iteration on which we will apply Conway's rules to derive Boolean on/off  mappings. That is, it's our cojoin of type of F[F[Boolean]] that needs to be flattened.

Memoization

Recalculating Conway's rules recursively is expensive. Without memoization, you'll see deep stacks. Using jconsole, I saw quite a few:

- eliminated <owner is scalar replaced> (a Store) at Store.counit(Life.scala:69)

which apparently "represents a redundant lock that has been removed in the bytecode." [SO]. This is because the code on each lookup is trying to recalculate the grid from scatch. Memoization prevents this by caching the grid of the last iteration.

What triggers this recalculation is the rendering of the 20x20 grid. This grid obviously leads to 400 evaluations. But the grid (Store) of each iteration has a reference its predecessor's 400 on which it must calculate Conway's rules. Not only do we not want to recalculate that grid from the game's beginning, we don't want to perform a further 3600 (=400 * 8 neighbours) calculation for cells we've already evaluated - hence the caching.