Safe Haskell | None |
---|---|

Language | Haskell2010 |

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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!