## Introduction

I’m going to talk a little bit about Conway’s Game of Life, comonads in practical use, and the performance improvement that they have to offer. If you already know what the GoL is, skip the introduction, and if you’re already familiar with comonads and how they are defined in Haskell, feel free to skip down to the performance section.

### What is the Game of Life?

Conway’s Game of Life is a cellular automaton of simple cells, each following simple rules, from which very complex behavior emerges under the right conditions. It is one of many examples of complex systems.

In a nutshell, there is a 2D grid of cells, each of which has two possible states: alive or dead.
The grid evolves in discrete steps of time `t`

. At time `t = 0`

,
we give the board some initial state. For all `t > 0`

,
the grid evolves to step `t + 1`

based on these simple rules:

- Any live cell with exactly two or three live neighbours stays alive.
- Any dead cell with exactly three live neighbours becomes alive.
- All other cells die.

### A naive implementation

Yesterday I finished a little terminal application
to play around with the GoL (link set to “initial” version before comonads).
As you can guess from the rules above, the GoL is very easy to program;
the difficulty is in programming it *efficiently*. One well known method
of computing the game is known as HashLife, which is a pretty objectively complex
technique. (Someone did this, or some of it, in Haskell
here.)

In my first pass at this, instead of creating a custom data structure directly I opted to leverage grid which is a really cool library that is useful for exploring mathematical grids/graphs/lattices:

It was nice to do this first because I got **a lot** for free.
Essentially my board looks like a mapping of `(x,y)`

coordinates to cell states.
In fact, the `toList`

function that we get from the `Grid`

typeclass confirms this:

I even get a `neighbours`

function that returns all 8 neighbours of a cell
along with many more useful functions, so implementing
game evolution was very straightforward:

Furthermore, using the toroidal style of grid allows modular boundaries which is how I wanted to implement this version.

So, you can see I was able to speed through the actual GoL logic since
most of the tedious legwork was done in the grid package.
My real challenge and where I spent the most effort was in the
frontend, rendering and handling user interaction from a terminal.
I chose to use brick
which is a *fantastic* package that provides
a high level declarative API to develop terminal interface applications
along with a number of useful widgets - not to mention 17 awesome
demo programs, great documentation, and a responsive google group.
If you’re curious, this
is how I rendered the above implementation using the brick library.
But, this post is not about brick. Maybe that will come in the future.

## Comonads

Like any good Haskeller I’d like to leverage whatever abstractions I can to improve the elegance and performance of this codebase. As it turns out, cellular automata are well represented by comonads.

### Definition

Let’s consider what the *dual* of the `Monad`

type looks like:

As anyone else on the internet would say, the *dual* of something
is when its “arrows are flipped around”, which at first sounds like handwavey
nonsense. Head here
for an excellent explanation of duality and how it applies to types in Haskell.
I don’t want to get lost in the forest or duplicate content on the internet,
so click that link or be satisfied with the fact that the arrows are literally
flipped in the type signatures above.

I don’t want to get bogged down in category theory land - if you want to go down that path, see my resources. Instead, let’s just build up intuition with some examples.

### Examples

The intuition we are trying to garner is that while monads *produce* effectful computations,
comonads are *consumed* in context-sensitive computations.
They usually come in handy when there is some large data structure that is composed
of small, similar computations. Sound familiar?

#### Stream

This is probably the simplest example, almost canonical to comonads:

So `extract`

is like `head`

and `duplicate`

is like `tails`

.
`extend`

on the other hand looks a little `fmap`

-y:

Well, it’s sort of similar to `fmap`

but the type signature is slightly different
in that the function argument `f :: Stream a -> b`

accepts its first
argument already of type `Stream a`

.
Consequently, `f`

can *know* or be *context-aware* of the comonadic structure
when it produces its return value of type `b`

. This is where the power of
comonad really shines. In this case, the context that `f`

is aware of
at *each* function call when mapping over the stream is a current element
`x`

(we’ll say at the current “cursor”) along with the whole tail of the list from
`x`

onwards.

This observation lends itself to the intuition we set out to build, namely that
monads *produce* additional context
while comonads are *consumed* within a context.

Note that `bind`

accepts a function `g :: a -> m b`

that takes an `a`

value and *produces* a contextual value `m b`

.
Contrast this with `extend`

accepting a function `f :: m a -> b`

which has `f`

*consuming* the contextual value `m a`

.

#### Zipper

Here’s what this looks like in practice:

Hopefully these examples show how comonads are a very fitting solution to computing cellular autamata. Again, refer to resources if you are unsatisfied, as there’s plenty of content to read up on.

### Applying to the Game of Life

I want to change as little as possible from my current implementation - ideally just swap out the data structure and change very little in my frontend and test suite. I hit this mark fairly well, as my commit updating the executable only diffs by +15/-17.

My implementation is similar to my sources, but unique in the toroidal aspect. My base 1-dimensional zipper is defined as

So “shifting left” will focus the first element of `_zl`

and snoc `_zc`

to `_zl`

,
while “shifting right” will focus the last element of `_zl`

and cons `_zc`

to `_zl`

.
I chose `Data.Sequence`

because it has a nice API and is symmetric in
time complexities when viewing either end of the sequence.

So the Game of Life is then implemented as a nested `Z (Z a)`

:

You might be wondering where that `Cell`

indexer comes into play.
I ended up creating a `Zipper`

class, which was a nice pattern because
once `Z`

had a `Zipper`

instance, I could easily polymorphically use those
class functions when writing the instance for the newtype `ZZ`

. The class
is larger than it needs to be, as I’m not even currently using all of its methods,
but I think it is fairly future proof if I want to add more features to the app:

I don’t want there to be a billion lines of code in this article, so feel free to check out the
source
if you want to see how those instances are defined for `Z`

and `ZZ`

.
Once they are defined, writing the `Comonad`

instance is much easier:

It looks a little messy, but that’s probably just me being an amateur.
Really all that `duplicate`

needs to do is, for all indices `(i,j)`

,
replace the element at `(i,j)`

with the argument `z`

shifted west `i`

times
and shifted south `j`

times; that is, the argument `z`

with cursor/index focused
at `(i,j)`

.

Finally, with `Zipper`

and `Comonad`

instances in place, here is the new `step`

:

## Performance

My profiling methodology for each of the scenarios below is to simply measure against the test suite, which does quite a bit of computing and comparison of evolved games. Below are the commands I used to generate the results:

### Initial

Here are some profiling details from the first implementation, which mapped across the board while performing lookups to retrieve the neighborhood values:

- Time: 13.22 secs
- Memory: 5.50 GB
- Spec.prof & Spec.ps

We see there is quite a bit of memory spent in the `step`

function.

### Comonads to the rescue

Now that the function evolving the game has cursor context
and easy access to each cursor’s neighborhood,
just a few `O(1)`

lookups at the front and back of `Data.Sequence.Seq a`

containers,
performance improves drammatically.

- Time: 1.08 secs
- Memory: 3.95 GB
- Spec.prof & Spec.ps

### Comparison

Running the test suite with the second data structure decreased the overall time by **92%**, the overall memory allocation by **28%**, and peak memory allocation by about **57%** .

## Further reading

For more in-depth reading on category theory and comonads, here are my sources:

- Duality for Haskellers - EZ Yang
- Flipping arrows in coBurger King - EZ Yang
- Comonad presentation - Kenny Foner
- ComonadSheet source code - Kenny Foner
- Another comonad presentation - David Overton