Game of Life implementation in Haskell

I've written a small Game of Life module in Haskell, as well as a small testing application. I'm relatively new to the language, so any kind of comment about the code is welcome. The most important comments for me are comments about efficiency of the code, and of course bugs. I would also be happy to accept comments about:

• Coding Style

• "Reinventing the wheel"

• Misuse of features

• Show instance efficiency

```
module GameOfLife
( State(..)
, Board
, evolve
, initBoard
, setStates
, nextGen ) where
import Data.List
import Data.Maybe
import qualified Data.Map as Map

data State = Alive | Dead deriving (Eq, Show)
type Coord = (Int,Int)
data Cell = Cell { cellState :: State
, cellCoord :: Coord } deriving Show
data Board = Board { boardGrid :: (Map.Map Coord Cell)
, boardWidth :: Int
, boardHeight :: Int}

initBoard :: Int -> Int -> Board
initBoard width height =
let grid = Map.fromList $ [(c, Cell Dead c) | x State -> Coord -> Board
setState (Board grid width height) state (x,y)
| y >= height || y = width || x State -> [Coord] -> Board
setStates board state = foldl (\board coord -> setState board state coord) board

neighbours :: Board -> Coord -> [Cell]
neighbours (Board grid width height) c@(x,y)
| not (inBounds c) = error "Coordinate off bounds"
| otherwise =
let neighboursCoords = filter (/= c) $ filter inBounds [(x',y') | x' = 0 && y >= 0 && x Board
nextGen board =
let
livingNeighbours c = length $ filter (==Alive) $ map cellState (neighbours board c)
takeState state = map cellCoord $ filter (\c -> cellState c == state) $ Map.elems $ boardGrid board
underPop = filter (\coords -> (livingNeighbours coords) (livingNeighbours coords) > 3) $ takeState Alive
newBorn = filter (\coords -> (livingNeighbours coords) == 3) $ takeState Dead
revive b = setStates b Alive newBorn
kill b = setStates b Dead (overPop ++ underPop)
in k

First of all you should consider how you represent your board.

• Using Array with two-dimension index (Ix) would be a good choice for the way you work right now. You define value for each cell individually no matter what is in that cell.

• Alternative way is to use Map to () or Set of coordinates to represent Alive cells while treating rest of the board as Dead.

• Yet another is to use own container without even mentioning of coordinates.

Consider the way how list ([a]) defined. That's actually a single-linked list. And you can create double-linked list like data DList a = DList DList a DList. In a same way you can define a double-linked grid (4 directions). Going further will let you define 5th dimension that represents generations.

Such approach often used to represent lazy infinite structures that grow while you walk over them (ex. you walk around some cell and then dive into next generation and walk around again revealing how everythin were changed).

I remember some term associated with that called "cellular automaton"

Next would be state (in case of Array and "cellular automaton")

Here you can define your own State just to make it clear, but you as well can use Bool. Note that it doesn't look like you need coordinates at all (consider dropping them from Cell).

Producing of new Map, Set, Array should be considered carefully I guess

One of the important thing is that its better to avoid producing of new board on each intermediate step (killing and reviving). I'd suggest to build up delta and then apply to original board. That should guard you from building almost similar copies of board.

Signatures

• It's a very common practice for update functions to take input as a last argument. I.e. setState :: State -> [Coord] -> Board -> Board. That allows to write something like: killTopLeft = setStates Dead [(0,0)]

Using high-order functions

evolve = iterate nextGen

And

setStates board state coords = Map.union updates board where
    updates = Map.fromList $ map (\c -> (c, Cell state c)) coords

StackExchange Code Review Q#39170, answer score: 4