使用 Store comonad 的 Conway 生命游戏的性能

Question

我写了一个简单的 Conway's Game of Life using the Store comonad (see code below). My problem is that the grid generation is getting visibly slower from the fifth iteration onwards. Is my issue related to the fact that I'm using the Store comonad? Or am I making a glaring mistake? As far as I could tell, other implementations 实现，它基于 Zipper comonad，非常高效。

import Control.Comonad

data Store s a = Store (s -> a) s

instance Functor (Store s) where
    fmap f (Store g s) = Store (f . g) s

instance Comonad (Store s) where
    extract (Store f a) = f a
    duplicate (Store f s) = Store (Store f) s

type Pos = (Int, Int)

seed :: Store Pos Bool
seed = Store g (0, 0)
    where
        g ( 0,  1) = True
        g ( 1,  0) = True
        g (-1, -1) = True
        g (-1,  0) = True
        g (-1,  1) = True
        g _        = False

neighbours8 :: [Pos]
neighbours8 = [(x, y) | x <- [-1..1], y <- [-1..1], (x, y) /= (0, 0)]

move :: Store Pos a -> Pos -> Store Pos a
move (Store f (x, y)) (dx, dy) = Store f (x + dx, y + dy)

count :: [Bool] -> Int
count = length . filter id

getNrAliveNeighs :: Store Pos Bool -> Int
getNrAliveNeighs s = count $ fmap (extract . move s) neighbours8

rule :: Store Pos Bool -> Bool
rule s = let n = getNrAliveNeighs s
        in case (extract s) of
            True  -> 2 <= n && n <= 3
            False -> n == 3

blockToStr :: [[Bool]] -> String
blockToStr = unlines . fmap (fmap f)
    where
        f True  = '*'
        f False = '.'

getBlock :: Int -> Store Pos a -> [[a]]
getBlock n store@(Store _ (x, y)) =
    [[extract (move store (dx, dy)) | dy <- yrange] | dx <- xrange]
    where
        yrange = [(x - n)..(y + n)]
        xrange = reverse yrange

example :: IO ()
example = putStrLn
        $ unlines
        $ take 7
        $ fmap (blockToStr . getBlock 5)
        $ iterate (extend rule) seed

Answer 1

store comonad 本身并不真正存储任何东西（除了抽象意义上的函数是一个“容器”），而是必须从头开始计算它。在几次迭代后，这显然变得非常低效。

不过，如果您仅使用 some memoisation:

备份 s -> a 函数，则可以在不更改代码的情况下缓解此问题

import Data.MemoTrie

instance HasTrie s => Functor (Store s) where
  fmap f (Store g s) = Store (memo $ f . g) s

instance HasTrie s => Comonad (Store s) where
  extract (Store f a) = f a
  duplicate (Store f s) = Store (Store f) s

尚未测试这是否真的提供了可接受的性能。

顺便说一下，Edward Kmett 有一个明确记忆的版本 in an old version of the comonad-extras package, but it's gone now. I've recently looked if that still works（在调整依赖关系后似乎是这样）。

使用 Store comonad 的 Conway 生命游戏的性能

Performance of Conway's Game of Life using the Store comonad

performance

haskell

comonad