haskell - 康威生命游戏递归阶跃函数

Question

为了帮助我开始理解 Haskell，我正在实现 Conway 的生命游戏，但在尝试构建 2D 列表的步骤函数中遇到了障碍。相关定义如下:

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

我的步骤功能是我遇到问题的地方。我不确定如何在没有相互递归的情况下构建我期望的 2D 列表(我试图任意避免)。

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

我期望来自step testBoard的以下输出:

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

但我得到的是:

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

我明白这是因为我的 step' 递归情况给出了 [(coord, newCell (numNeighbors board coord) cell)] : ...，但是如果我拉在列表之外我收到以下错误:

[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.

Answer 1

step' 的最后一个方程是错误的。

step' (((coord, cell):restrow):rest) = [(coord, newCell (numNeighbors board coord) cell)] : (step' (restrow:rest))

对于每行中的每个单元格，您都会生成一个新的单单元格行作为输出。如果您坚持手动编写所有递归，则可以通过 cons 到递归调用返回的第一行来解决此问题，而不是每次都创建新行:

step' :: IndexedBoard -> IndexedBoard
step' [] = []
step' ([]:rest) = [] : step' rest
step' (((coord, cell):restrow):rest) = 
  let (row:more) = step' (restrow:rest)
  in ((coord, newCell (numNeighbors board coord) cell) : row) : more

但是，有一种更好的方法:您所做的就是尝试将函数应用于嵌套列表中的每个 (Coord, Cell) 对，同时维护列表的结构。但这正是 map 的用途!您应该定义一个更简单的函数来更新列表中的单个条目，然后将其映射到所有条目上:

updateCell :: (Coord, Cell) -> (Coord, Cell)
updateCell (coord, cell) = (coord, newCell (numNeighbors board coord) cell)

step' :: IndexedBoard -> IndexedBoard
step' = map (map updateCell)