人生的游戏，真正的无限的棋盘

Question

生命游戏通常是通过将董事会表示为二维布尔数组来实现的。它不能很好地扩展到更大的板上--它开始消耗大量的内存，如果没有某种独立的机制来跟踪一个活细胞列表，你就必须在每次迭代中访问每个板单元。此实现只保留一个表示板状态的活动单元格列表；板“大小”仅受整数最大值的限制。

import Data.List as L
import Data.Map  as M

type Coo = (Int,Int)
type Board = Map Coo Int

moveBoard::Coo->Board->Board
moveBoard (dx,dy) = M.mapKeysMonotonic (\(x,y)->(x + dx, y + dy))

countNeighbors::Board->Board
countNeighbors b =
  unionsWith (+) [ moved (-1, -1),  moved (0, -1),  moved (1, -1),
                   moved (-1,  0),                  moved (1,  0),
                   moved (-1,  1),  moved (0,  1),  moved (1,  1) ]
    where moved (dx, dy) = moveBoard (dx, dy) b

lifeIteration::Board->Board
lifeIteration b = M.union birth survive
  where neighbors = countNeighbors b
        birth     = M.map (const 1)  (M.filter (==3) neighbors)
        survive   = M.intersection b (M.filter (==2) neighbors)

glider = M.fromList $ L.map (\(x,y)->((x,y),1::Int)) ([(1,1),(1,2),(1,3),(2,3),(3,2)]::[(Int,Int)])

Answer 1

编辑:这个答案是在评审代码看起来完全不同的时候给出的。

有什么具体问题吗？以下是我的突出之处：

1. 为什么toList在emptyNeighbors，然后又回到Set？您只需在那里使用Data.Set.map即可。
2. countNeighbor效率很低：filter操作总是在所有生命单元上迭代，每一个现有的单元格都要调用它三次！这是不必要的，因为你只关心过几个邻居的牢房。

我解决问题2的想法是构建一个每个单元的邻居计数的Map。如果您将董事会表示为一个只有Map单元格的1，那么使用mapKeysMonotonic和unionsWith可以非常有效地完成这一任务：

type Coo = (Int, Int)
type Board = Map Coo Int

moveBoard :: Coo -> Board -> Board
moveBoard (dx,dy) = M.mapKeysMonotonic (\(x, y) -> (x+dx, y+dy))

countNeighbours :: Board -> Board
countNeighbours b =
  unionsWith (+) [ moved (-1) (-1), moved 0 (-1), moved 1 (-1)
                 , moved (-1)   0 ,               moved 1  0
                 , moved (-1)   1 , moved 0   1 , moved 1  1   ]
 where moved dx dy = moveBoard (dx,dy) b

注意，使用mapKeysMonotonic是安全的，因为当我们添加一个常量时，坐标的顺序不会改变。实际上，这意味着库可以简单地替换具体的坐标，而无需任何内部求助。

然后，对结果使用filter、map和intersection是一个简单的问题：

lifeIteration :: Board -> Board
lifeIteration b = M.union birth survive
 where neighbours = countNeighbours b
       birth      = M.map (const 1)  (M.filter (==3) neighbours)
       survive    = M.intersection b (M.filter (==2) neighbours)

用三个邻居的“重生”来改变你的配方，而不是生存，因为这样写起来要简单一些。

还请注意，通过利用intersection总是返回第一个Map的值这一事实，这有点“聪明”，因此我不需要在其中执行另一个M.map (const 1)步骤。

我希望这对你有帮助。