{-| This module walks through implementing <https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life Conway's Game of Live> using @grids@. Read this module from top to bottom -} {-# LANGUAGE DataKinds #-} {-# LANGUAGE OverloadedLists #-} {-# LANGUAGE ViewPatterns #-} module Data.Grid.Examples.Conway where import Data.Grid import Data.Foldable import Data.List import Data.Functor.Compose {-| Conway's game of life is a form of <https://en.wikipedia.org/wiki/Cellular_automaton 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. -} step :: (IsGrid dims) => Grid dims Bool -> Grid dims Bool step = autoConvolute @[3, 3] wrapBounds rule {-| 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. -} 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 {-| 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' > [ ".#........" > , "..#......." > , "###......." > , ".........." > , ".........." > , ".........." > , ".........." > , ".........." > , ".........." > , ".........." > ] -} start :: Grid '[10, 10] Bool start = (== '#') <$> fromNestedLists' [ ".#........" , "..#......." , "###......." , ".........." , ".........." , ".........." , ".........." , ".........." , ".........." , ".........." ] {-| 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 -} simulate :: Int -> Grid '[10, 10] Bool simulate i = iterate step start !! i {-| 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! -} showGrid :: (IsGrid '[x, y]) => Grid '[x, y] Bool -> String showGrid = intercalate "\n" . toNestedLists . fmap showBool where showBool :: Bool -> Char showBool True = '#' showBool False = '.'