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.
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.
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.
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?
This is probably the simplest example, almost canonical to comonads:
extract is like
duplicate is like
extend on the other hand looks a little
Well, it’s sort of similar to
but the type signature is slightly different
in that the function argument
f :: Stream a -> b accepts its first
argument already of type
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
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.
bind accepts a function
g :: a -> m b
that takes an
a value and produces a contextual value
Contrast this with
extend accepting a function
f :: m a -> b
f consuming the contextual value
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
while “shifting right” will focus the last element of
_zl and cons
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
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
if you want to see how those instances are defined for
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
replace the element at
(i,j) with the argument
z shifted west
and shifted south
j times; that is, the argument
z with cursor/index focused
Comonad instances in place, here is the new
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:
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
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
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% .
For more in-depth reading on category theory and comonads, here are my sources: