Исполнение игры Конвея «Жизнь» с использованием комонады Store

Я написал простую реализацию Игры жизни Конвея, используя Сохранить comonad (см. код ниже). Моя проблема в том, что генерация сетки становится заметно медленнее, начиная с пятой итерации. Связана ли моя проблема с тем, что я использую комонаду Магазина? Или я совершаю вопиющую ошибку? Насколько я мог судить, другое , основанные на комонаде Zipper.

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

performance haskell comonad
person Dan Oneață    schedule 04.08.2017    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Комонада store сама по себе ничего не хранит (кроме абстрактного смысла функции как «контейнера»), но должна вычислять ее с нуля. Это явно становится очень неэффективным через пару итераций.

Однако вы можете облегчить это без изменения кода, если просто создадите резервную копию функции 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

Не проверял, действительно ли это дает приемлемую производительность.

Между прочим, у Эдварда Кметта была явно запомненная версия в старой версии пакета comonad-extras, но сейчас его нет. Недавно я проверил, работает ли это по-прежнему (похоже, работает после настройки зависимостей).

person leftaroundabout    schedule 04.08.2017