Data.Grid.Examples.Conway

This module walks through implementing Conway's Game of Live using grids. Read this module from top to bottom

Documentation

step :: IsGrid dims => Grid dims Bool -> Grid dims Bool

Conway's game of life is a form of Cellular Automata; This means that it's a system of cells where a simulation is described in terms of the neighbourhood of a cell. We'll implement the standard set of rules for Conway's Game of Life using convolution with grids (which you can read about on wikipedia)!

grids provides the convolute and autoConvolute helpers to allow performing neighbourhood-aware computations without too much trouble.

autoConvolute allows you to provide a window-size via a Type Application, a function for adapting the coordinates of the neighbours, which is useful for providing behaviour for cases where coordinates are out of bounds. Lastly we provide a function which can reduce the provided neighbourhood of a cell back down to a single cell which will be slotted into the final structure.

With these things in mind, we write our step function which performs a single simulation step on a Grid using a window-reduction rule that we'll write next!

step :: (IsGrid dims) => Grid dims Bool -> Grid dims Bool
step = autoConvolute @[3, 3] wrapBounds rule

We use the wrapBounds strategy for handling out-of-bounds indices which will occur when trying to get the neighbourhood of cells along the edge of the grid. wrapBounds means we'll grab the next cell from the opposite side of the grid, wrapping around Pacman style.

rule :: Grid [3, 3] Bool -> Bool

Next up we'll write the reduction rule itself. We've already decided to use a [3, 3] neighbourhood in the previous step by using a Type Application, GHC could infer it in thi case if we didn't provide it; but I find it helpful to be as clear as possible.

So the goal is to go from a [3, 3] neighbourhood of a cell down to a single cell again; the liveness of each cell is a Bool which is True if the cell is alive, False otherwise.

Take a look at how we do it:

rule :: Grid [3, 3] Bool -> Bool
rule window' =
  (currentCellAlive && livingNeighbours == 2) || livingNeighbours == 3
  where
    (currentCellAlive, neighbours) = partitionFocus window'
    livingNeighbours = length . filter id . toList . Compose $ neighbours

We'll start with the where clauses.

Firstly we use the nifty partitionFocus combinator which separates out the center of a window from the surrounding neighbours as a tuple. Intuitively, We name these parts currentCellAlive and neighbours. Next we count how many neighbours are actually alive by leaning on the Foldable typeclass. partitionFocus returns the neighbours as a Grid [3, 3] (Maybe Bool) in this case; so by wrapping it with Compose we can fold over only the Just values, e.g. the neighbours! We then filter out the False ones with filter id and we know how many neighbours are alive!

Back to the main definition, all that's left is to write the actual logic of the rule; there are many ways to write in the rule; but I hope you trust I've picked a good one :D

That's it! By combining our rule with the powers of auto-convolution we've written the core of Conway's game of life in just a dozen lines of code. Clever us!

Keep reading and we'll add some helpers so we can actually try running it.

start :: Grid '[10, 10] Bool

If we're going to simulate a game we need to have a starting position!

Let's start off with a glider hanging out in the top left corner.

Since we'll be using a 2 dimensional grid we can draw out our grid as a list of lists (i.e. [String]) and use fromNestedLists' to build it into a Grid for us! Note that the trailing ' denotes the unsafe version of fromNestedLists which will error if we give it input that mismatches our expected dimensions, use the safe version unless you're confident about your input sources!

start :: Grid '[10, 10] Bool
start = (== '#') <$> fromNestedLists'
  [ ".#........"
  , "..#......."
  , "###......."
  , ".........."
  , ".........."
  , ".........."
  , ".........."
  , ".........."
  , ".........."
  , ".........."
  ]

simulate :: Int -> Grid '[10, 10] Bool

Now that we've got a good starting point we can run a few steps of our simulation and see where we end up!

step is an Endomorphisn, i.e. a function from a type to the same type, so we can use iterate to generate an infinite list of steps where each subsequent step is equal to applying the step function on the previous iteration.

By using !! we can index into the infinite list and see what things look like after a set number of iterations.

simulate :: Int -> Grid '[10, 10] Bool
simulate i = iterate step start !! i

showGrid :: IsGrid '[x, y] => Grid '[x, y] Bool -> String

The built-in show instance for Grid isn't perfect, so let's write a nice one for our simulation. We can extract our grid as a list of lists of Bool, i.e. [[Bool]]; and collapse it into a string so we can print it to the console.

showGrid :: (IsGrid '[x, y]) => Grid '[x, y] Bool -> String
showGrid = intercalate "\n" . toNestedLists . fmap showBool
  where
    showBool :: Bool -> Char
    showBool True = '#'
    showBool False = '.'

Let's how far our glider can make it to after 10 iterations

λ> putStrLn . showGrid $ simulate 10
..........
..........
..........
....#.....
..#.#.....
...##.....
..........
..........
..........
..........

That's it for this guide! Thanks!