소개

이 기사는, 「코모나드를 사용한 추상화의 위력을 라이프 게임에서 시험해 보았다 」로 언급되고 있는 「토러스상의 List Zipper」를 구현해 보았습니다, 라고 하는 기사입니다. Comonad로 구현한 List Zipper를 사용하여 라이프 게임을 구현했으며 메모리 사용량이 증가하지 않는 것을 확인했습니다.

토러스란?

직사각형의 좌변과 우변, 상변과 하변이 각각 연결되어 있는 구조입니다. RPG의 평면 맵에서, 우단이나 상단에 가면 각각 좌단이나 하단으로부터 나오는 것 같은 상황을 상상하면 알기 쉽다고 생각합니다(평평하게 말하면 도넛 모양의 구조입니다).

구현 포인트

List Zipper 정의(1차원)

토러스상(2차원)의 List Zipper를 생각하기 전에, 링상(1차원)의 List Zipper를 생각해 봅시다.
직선의 List Zipper를 사용하면 관심 지점을 어디까지나 이동할 수 있지만 반지에서 목록의 길이만큼 관심 지점을 이동하면 되돌아갑니다.
그러므로 어느 한 방향으로만 이동할 수 있으면 충분합니다.
또, 주목점의 옆에 대해서도, 꺼내기 쉽게 해 두는 것이 나중에 편리합니다.
따라서 링의 List Zipper를 다음과 같이 정의합니다.

Main.hs

data Z a = Z a a [a] deriving Show

next :: Z a -> Z a
next (Z y x xs) = let xss = xs ++ [y]
                  in Z x (head xss) (tail xss)

여기서, Z a a [a] 는 (주목점의 전) (주목점) (주목점의 한 후:_)이 되어 있습니다.

Comonad 구현

직선상의 List Zipper에서는, duplicate 할 때 iterate1 함수를 사용해, 주목점의 좌우에 List Zipper의 무한 리스트를 작성하고 있습니다.
반면에 링의 List Zipper는 유한 회의 주의점을 어긋나면 되돌아가기 때문에 duplicate로 작성된 List Zipper의 리스트는 유한의 길이여야 합니다.
위의 이유로 List Zipper를 Comonad의 인스턴스로 사용하면 다음과 같습니다.

Main.hs

iterateN :: Int -> (a -> a) -> a -> [a]
iterateN 0 _ _ = []
iterateN n f x = let z = f x
                 in z : iterateN (n-1) f z

instance Functor Z where
  fmap f (Z y x xs) = Z (f y) (f x) (fmap f xs)

instance Comonad Z where
   extract (Z _ x _) = x
   duplicate zt@(Z _ _ xs) = let ztt = (iterateN (length xs + 1) next zt)
                             in Z (last ztt) zt (init ztt) 

iterateN 함수를 사용하여 함수의 반복 적용을 유한회로 중단하는 곳이 포인트입니다.

List Zipper 정의 (2D)

토러스의 List Zipper에 대해서도 1차원의 경우와 같은 아이디어로 구현할 수 있습니다. 가로 방향을 링 모양으로 했으므로, 세로 방향도 링 형상으로 해 줍니다.
구체적인 구현은 다음과 같습니다.

Main.hs

newtype Z2 a = Z2 (Z (Z a)) deriving Show

instance Functor Z2 where
   fmap f (Z2 zz) = Z2 (fmap (fmap f) zz)

instance Comonad Z2 where
  extract (Z2 zz) = extract (extract zz)
  duplicate (Z2 zz) = fmap Z2 . Z2 . roll . roll $ zz
  where roll zt@(Z _ (Z _ _ xs) _) = let ztt = (iterateN (length xs + 1) (fmap next) zt)
                                     in Z (last ztt) zt (init ztt)

움직여 보면

이런 느낌입니다 (촬영의 사정으로, 조금 부서져 버리고 있습니다.또, 이상한 곳에서 날고 있습니다).
덧붙여 평면상의 List Zipper에서는 주목점의 우측/하측만 그리면 충분했습니다만, 토러스상의 List Zipper는 주목점도 포함해 모두 묘화 할 필요가 있습니다.

마지막으로

이번에는 토러스에 List Zipper를 Comonad로 구현하고 라이프 게임에서 놀아 보았습니다. lotz 씨도 쓰고 있었습니다만, extend life 그냥 전체의 갱신을 할 수 있는 것은 조금 감동하네요.

또, 토러스상에서의 계산은, 말투를 바꾸면(자) 주기적 경계 조건하에서의 계산이며, 수치 시뮬레이션으로서는 비교적 자주(잘) 있는 설정이기도 합니다. 이번 응용으로서 2차원의 Ising Model의 계산 등도 비교적 간단하게 구현할 수 있을 것 같습니다.

이번 코드는 아래에 있습니다 (계산 내용만 동영상으로 바꾸고 있습니다).
그대로 stack ghc Main.hs 하면 움직인다고 생각됩니다.
htps : // 기주 b. 코 m/츄파아아아아안/ぃふぇ가메/bぉb/마s테 r/마인. hs

이상입니다.