トーラス上のライフゲームを、List Zipperを使用して実装してみた

はじめに

この記事は、「コモナドを使った抽象化の威力をライフゲームで試してみた」で言及されている「トーラス上の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]は(注目点の1つ前) (注目点) (注目点の1つ後:_)となっています。

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の定義(2次元)

トーラス上の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すれば動くと思われます。
https://github.com/chupaaaaaaan/lifegame/blob/master/Main.hs

以上です。