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
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 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)!
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.
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.
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.