Conway's Game of Life recursive step function

Question

To help me begin to understand Haskell, I'm implementing Conway's Game of Life and ran into a snag in my step function trying to build a 2D list. Relevant definitions below:

data Cell = On | Off deriving (Eq, Show)

type Board = [[Cell]]
type Coord = (Int, Int)
type IndexedBoard = [[(Coord, Cell)]]

testBoard =     [[On, On,  On]
                ,[On, Off, On]
                ,[On, On,  On]]

numNeighbors :: Board -> Coord -> Int
-- Returns the number of live neighbors given a Board and a Coord on that board
-- assume this is implemented correctly, because it's a bunch of code
-- that you don't otherwise need to read, and it passes tests.

addIndexes :: Board -> IndexedBoard
addIndexes xs = [[((x,y), el) | (x,el) <- zip [0..] row] | (y,row) <- zip [0..] xs]
removeIndexes :: IndexedBoard -> Board
removeIndexes = map (map snd)
-- addIndexes testBoard is
-- [ [((0, 0), On), ((1, 0), On),  ((2, 0), On)]
--   ,((0, 1), On), ((1, 1), Off), ((2, 1), On)]
--   ,((0, 2), On), ((1, 2), On),  ((2, 2), On)] ]
-- and removeIndexes . addIndexes = id

My step function is where I'm having trouble. I'm not sure how to build the 2D list I expect without mutual recursion (which I'm trying to avoid arbitrarily).

step :: Board -> Board
step board = removeIndexes . step' . addIndexes $ board where
    step' :: IndexedBoard -> IndexedBoard
    step' [] = []
    step' ([]:rest) = step' rest
    step' (((coord, cell):restrow):rest) = [(coord, newCell (numNeighbors board coord) cell)] : (step' (restrow:rest))
    newCell :: Int -> Cell -> Cell
    newCell 2 On = On
    newCell 3 _ = On
    newCell _ _ = Off

I expect the follow output from step testBoard:

[[On,  Off, On ]
,[Off, Off, Off]
,[On,  Off, On ]]

But am instead getting:

[[On],  [Off], [On]
,[Off], [Off], [Off]
,[On],  [Off], [On]]

I understand that's because my recursive case of step' gives [(coord, newCell (numNeighbors board coord) cell)] : ..., but if I pull that out of the list I get the following error:

[1 of 1] Compiling Main             ( gameoflife.hs, interpreted )

gameoflife.hs:51:44: error:
    • Couldn't match type ‘(Coord, Cell)’ with ‘[(Coord, Cell)]’
      Expected type: IndexedBoard
        Actual type: [(Coord, Cell)]
    • In the expression:
        (coord, newCell (numNeighbors board coord) cell)
        : (step' (restrow : rest))
      In an equation for ‘step'’:
          step' (((coord, cell) : restrow) : rest)
            = (coord, newCell (numNeighbors board coord) cell)
              : (step' (restrow : rest))
      In an equation for ‘step’:
          step board
            = removeIndexes . step' . addIndexes $ board
            where
                step' :: IndexedBoard -> IndexedBoard
                step' [] = []
                step' ([] : rest) = step' rest
                step' (((coord, cell) : restrow) : rest)
                  = (coord, newCell (numNeighbors board coord) cell)
                    : (step' (restrow : rest))
                newCell :: Int -> Cell -> Cell
                newCell 2 On = On
                newCell 3 _ = On
                newCell _ _ = Off

gameoflife.hs:51:96: error:
    • Couldn't match type ‘[(Coord, Cell)]’ with ‘(Coord, Cell)’
      Expected type: [(Coord, Cell)]
        Actual type: IndexedBoard
    • In the second argument of ‘(:)’, namely
        ‘(step' (restrow : rest))’
      In the expression:
        (coord, newCell (numNeighbors board coord) cell)
        : (step' (restrow : rest))
      In an equation for ‘step'’:
          step' (((coord, cell) : restrow) : rest)
            = (coord, newCell (numNeighbors board coord) cell)
              : (step' (restrow : rest))
Failed, modules loaded: none.

Conway's Game of Life recursive step function

2 Answers