Ответ 1
Хорошо, я разочарован тем, что никто еще не дал "правильный" ответ на эту проблему, потому что я знаю, что он существует, но я не смогу это объяснить. Мой ответ основан на http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html
Прежде всего, стандартом, который является 1-й молнией, может быть:
Data U x = U [x] x [x]
первый элемент - это обратный список всех элементов, "левый" фокус, затем элемент фокусировки, затем список всех элементов "справа" фокуса. Например:.
U [-1,-2,-3] 0 [1,2,3]
Затем мы можем переместить молнию влево и вправо. Вы должны решить, что делать, когда мы убегаем от края сетки. Первоначальное сообщение просто постулировало бесконечную сетку, так что краевой регистр оставлен как упражнение для читателя.
left (U (a:as) x zs) = U as a (x:zs)
right (U as x (z:zs)) = U (x:as) z zs
Теперь все, что выглядит как контейнер, должно быть Functor так:
instance Functor U where
fmap f (U a x z) = U (map f a) (f x) (map f z)
В этот момент я действительно хочу, чтобы кто-то еще вошел, чтобы объяснить, что я собираюсь делать и почему. Я собираюсь сделать U экземпляр Control.Comonad. Лучшее, что я могу объяснить, это то, что комонады - это разновидность наизубых монадов. Вместо того, чтобы дать вам один элемент и попросить создать контейнер с новым значением (>>= :: Monad m => m a -> (a -> m b) -> m b), Comonads даст вам всю структуру и попросит только значение, которое принадлежит фокусу: (=>>) :: Comonad w=>w a -> (w a -> b) -> w
Итак, используя термины Control.Comonad в пакете comonad-3.0.2:
Instance Comonad U where
-- extract :: U a -> a -- called coreturn in the post
extract (U _ x _) = x
-- duplicate :: U a -> U (U a) -- called cojoin in the post
duplicate x = U (tail $ iterate left x) x (tail $ iterate right x)
duplicate дает вам молнию молнии, каждая из которых сдвигается влево или вправо еще одним элементом, а затем последним. Это кажется огромным объемом памяти, но Haskell ленив, и фактический объем памяти очень мал и порядка O (n) для полного набора и O (1), если вы вообще не смотрите вокруг.
Но это все в одном измерении. Опять же по причинам, я недостаточно умен, чтобы объяснить, что это расширение до двух измерений id dead easy:
data U2 x = U2 (U(U x))
instance Functor U2 where
fmap f (U2 y) = U2 $ fmap (fmap f) y
instance Comonad U2 where
extract (U2 y) = extract (extract y)
duplicate (U2 y) = fmap U2 $ U2 $ roll $ role y where
iterate' f = tail . iterate f
role x = U (iterate' (fmap left) x) x (iterate' (fmap right) x)
Дублирующая функция теперь создает сетку сеток, каждая из которых соответственно сдвигается. Так
goLeft u = let (U _ (U x _ _) _) = duplicate u in x
goRight u = let (U _ (U _ _ x) _) = duplicate u in x
goUp = left . duplicate
goDown = right . duplicate
here = extract
Поскольку Haskell ленив, все это O (1). Еще более интересно вы можете изменить here на O (1) стоимость как во времени, так и в памяти и использовать ячейки окрестности в вычислении. Это делает что-то вроде клеточного автомата game of life так же просто, как
rule (U2 (U
(U (u0:_) u1 (u2:_):_)
(U (u3:_) u4 (u5:_))
(U (u6:_) u7 (u8:_):_))) =
let n = length $ filter id [u0,u1,u2,u3,u5,u6,u7,u8] in
u4 && (n==2 || n==3) || (not u4) && n==3
-- assume u is the original graph each step is
step u = u =>> rule
В дополнение к сообщению в блоге выше, я предлагаю искать Google для Comonad, чтобы узнать больше, особенно, поскольку я не лучший, объясняя это.