Conway's Game of Life using Haskell and Gloss

• by Alejandro Serrano
• •
• November 26, 2019
• •
• haskell• functional programming• functional
• |
• 15 minutes to read.

This article is part of our series on Functional Programming solutions for the Global Day of Coderetreat challenge.

In the previous post of this series, we have seen how to use comonads in Swift to code Conway’s Game of Life. In this post, we take an entirely different direction: We start with a very naive and very underperformant solution, and change it in a calculational way to become much faster (by “calculational” we mean that each step is simple and direct, as replacing “1+1” with “2” in a calculation). In addition, we look at how to set up a simple UI using Gloss. The code is going to look incredibly similar to the SwiftUI approach. And, by the way, we are going to use Haskell instead of Swift.

You always need some data types

In typed functional programming – Haskell, Swift, Kotlin, Scala – the choice of data types usually guides your solution. In the solution in Swift, we had a notion of focused grid, which led to the definition of a comonad. In our case, the grid is going to be a mapping from points to one of the two possible cell status: either alive or dead. This mapping is going to be represented directly as a function.

-- | A point in the grid
type Point = (Integer, Integer)
-- | The status of a cell
data Cell = Alive | Dead deriving Eq
-- | Description of a grid
type Grid = Point -> Cell

Even if you only care about a small section of the grid, you need to take more and more of the surroundings into account; the other option being to crop a section of the board you care about. Using Haskell’s ability to manipulate infinite structures, we do not need to perform any cut-off.

To avoid Boolean blindness, we use a custom Cell data type, instead of Bool, to represent the status of a cell. The good news is that this does not degrade performance; in fact, the in-memory representation of Bool and Cell is exactly the same, since they are both data types with two constructors with no attached fields to any of it.

The naive solution

We want to define the Game of Life as a single function, which, given the initial grid and the number of steps to compute, gives us the corresponding state of the grid. In other words, we want a function with the following type:

gameOfLife :: Grid -> Integer -> Grid

The first line of the function tells us that, on step 0, the grid is just the initial grid. In this definition, we make use of the fact that Grid is actually a function; we can access the additional parameter directly as an argument.

gameOfLife initial 0 p
  = initial p

The second branch is the most direct translation one could make of the rules of the game. We define a local function nextStep, which implements the different scenarios from the announcement post. In order to make an informed choice, this function requires the previous status of the cell, and the previous status of all adjacent cells, which we obtain by calling gameOfLife recursively.

gameOfLife initial n p
  = nextStep (gameOfLife initial (n-1) p)
             (map (gameOfLife initial (n-1)) (adjacents p))
  where
    nextStep :: Cell -> [Cell] -> Cell
    nextStep Alive adj
      | count Alive adj < 2  = Dead  -- underpopulation
      | count Alive adj > 3  = Dead  -- overpopulation
      | otherwise            = Alive  -- live and let live
    nextStep Dead adj
      | count Alive adj == 3 = Alive  -- reproduction
      | otherwis e           = Dead  -- nothing happens
    
    -- count the number of elements that are equal to the given one
    count :: Eq a => a -> [a] -> Int
    count x = length . filter (== x)

The new status of each cell depends on the previous status of its adjacent cells. In order to obtain the position of these adjacent cells, we have defined an auxiliary function.

    -- continues where block from above
    adjacents :: Point -> [Point]
    adjacents (x,y)
      = [(x+m, y+n) | m <- [-1,0,1], n <- [-1,0,1], (m,n) /= (0,0)]

This solution implements Game of Life correctly, but unfortunately computes the same data over and over. For example, two adjacent cells in the grid share most of their adjacents, but the outcome of computing them in one call is not shared with the other. Also, if we compute the values for step 2, these are not kept when computing step 3. Too much wasted time (and energy)!

Here we go!

Before we turn to the meat of our solution, let us transform our function slightly. If you look carefully at the recursive calls to gameOfLife, you will notice that we always pass the initial grid unmodified. We can avoid that problem by defining a local function that closes over that argument.

gameOfLife initial = go
  where
    go 0 p
      = initial p
    go n p
      = nextStep (go (n-1) p)
                 (map (go (n-1)) (adjacents p))
    -- ... rest of the previous where block

We call this function go. As we intended, all occurrences of gameOfLife initial are now replaced by go. The base case still has access to the initial grid, because it is in scope.

Memoize all your codes

Wouldn’t it be great if we could keep the function as it stands now, but share all the intermediate values between calls? Fortunately, that is not black magic. That is a well-known optimization technique called memoization. Wikipedia could not be more clear about it:

In computing, memoization or memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

There are several Haskell libraries for memoizing functions (almost) automatically. MemoTrie, which stores intermediate results in a trie, will fit our needs. We only need to add a call to the corresponding version of memo at the top of your function:

gameOfLife initial = memo2 go

One moment to put on some gloss

We are ready to show our results, and we are going to do so with the awesome Gloss library. In particular, we are going to use their support for animations, that is, images that change over time.

animate :: Display              -- ^ Display mode.
        -> Color                -- ^ Background color.
        -> (Float -> Picture)   -- ^ Function to produce the next frame.
                                --   It is passed the time since the program started.
        -> IO ()

Gloss also provides a SwiftUI-like, React-like, interface for interactive programs and games, but this is not needed in this example.

We are going to divide the work in two functions. The first one, gameOfLifePicture, turns an already-computed Grid into a picture. We decide to focus only on the part of the grid from (-50, -50) to (50, 50), and for each of those points, we generate a solid rectangle of the corresponding color.

gameOfLifePicture :: Grid -> Picture
gameOfLifePicture g
  = pictures [ translate (fromInteger x * dIMENSION)
                         (fromInteger y * dIMENSION)
                         (color c (rectangleSolid dIMENSION dIMENSION))
             | x :: Integer <- [-50 .. 50]
             , y :: Integer <- [-50 .. 50]
             , let c = chooseColor (g (x, y)) ]
  where chooseColor Alive = red
        chooseColor Dead  = blue

The code is not as pretty as it could be, though, because of the lack of implicit conversion between numeric types. In our case, the cell coordinates are integers, but translate takes floating-point numbers as parameters. Haskell, being strongly-typed, requires a explicit call to fromInteger to convert from one to the other.

We have set the dimension of the squares representing each cell arbitrarily to 20 points. With that value, some of the cells may not be represented on the screen, but we have decided that a more complex algorithm to detect which part of the grid to show is not worth the effort.

dIMENSION :: Float
dIMENSION = 20

The second function, gameOfLifeAnimation, decides which Grid to show at each moment of time. To keep things simple, we are going to use a simple mapping: A new state is shown every half second, or seen from another angle, the generation to show at each moment is obtained by doubling the elapsed time.

gameOfLifeAnimation :: (Integer -> Grid) -> Float -> Picture
gameOfLifeAnimation f t
  = let time = floor (2 * t)
    in pictures [ gameOfLifePicture (f time)
                , color green (text (show time)) ]

There is a technical reason why we do not call gameOfLife directly in this function, but instead take a function as argument. In order to take advantage of memoization, we need all the calls to gameOfLifeAnimation to share the same function; otherwise, we are only memoizing per iteration.

The top-level main function is responsible for creating that shared function, which we simply call f in the code below:

main :: IO ()
main = do
  initial <- loadInitialGrid
  let f = gameOfLife initial
  animate FullScreen white (gameOfLifeAnimation f)

We have omitted the code for loading a grid from a file given as command line argument. The interested reader can consult the complete implementation, which is available on-line.

More sharing leads to a happier life

Now, of course, you want to run the code. If you have an incredibly powerful computer, you might get to the second iteration. What did we do wrong? The problem is that our function is memoized as a whole, but not during recursive calls. In fact, we are not taking advantage at all from the memoization!

Looking at the documentation of MemoTrie, we find a small pearl, memoFix. If you have never heard of it, fix is Haskell’s codename for “something which has to do with recursion.” The name comes from the notion of a fixed point of a function. You can read more here. All we need to know right now is how to use fix to declare a recursive function.

Let me use a quite simple function: one that adds one to each element of a list:

addOne :: [Integer] -> [Integer]
addOne []     = []
addOne (x:xs) = x + 1 : addOne xs

It is clear that we can implement this function as map (+1), but in this case, we are really interested in the recursive solution. In order to use fix, we define a new function, but one in which the recursive calls are replaced by an additional argument:

addOne = fix go
  where
    go r []     = []
    go r (x:xs) = x + 1 : r xs

The magic in fix is able to make call go again when you call r in the code. This transformation is calculational, and can be done with any recursive function.

In particular, let’s use it in our gameOfLife function. We have taken the liberty of using memoFix instead of fix, since we already know that memoization is really needed in this program:

gameOfLife :: Grid -> Integer -> Grid
gameOfLife initial = curry (memoFix go)
  where
    go _r (0, p)
      = initial p
    go r (n, p)
      = nextStep (r (n-1, p))
                 (map (\x -> r (n-1, x)) (adjacents p))
    -- ... rest of the previous where block

We used to have two places in which go was recursively called, so we now have two calls to r. In addition, we have decided to put both arguments in a tuple, just because it makes working with fixed points a bit simpler. Since go now takes a tuple as argument, we need to wrap the top-level call with curry to make it take two arguments instead.

Conclusion

When we apply the final change with memoFix, we go from two iterations to around 60 iterations until the computer explodes again. This time, the problem is that we are keeping so much information around that we eat up all the available memory. Keeping better track of what information we need and what information we don’t would lead us to the desired constant memory usage.

In any case, the secret goal of this post was not to teach you about how to create a performant Game of Life (since it blatantly fails on that respect), so much as it was to teach you about memoization and fixed points. In addition, we have seen an example of how an almost direct translation from rules to code is possible when using Haskell. In most cases, that solution is not fast enough, but serves very much as a testbed for further improvements.