Haskell (GHCi) でライフゲーム

## 動機

[OCaml の勉強のためにライフゲームを書いてみた](https://qiita.com/tadashi9e/items/07d94efb879fb6323244) のですが、Python で書いたのものに比べるとコード量が多くなってしまいました。

リスト内包表記がある言語ならもっと Python でのそれに近づけることができるのではないか、ということで、GHCi で書いてみることにしました。

## リスト内包表記

リスト内包表記は GHC の拡張機能として使えるようです。ghci コマンド起動時に

~~~sh
ghci -XParallelListComp
~~~

のようにすると ParallelListComp 拡張が利用可能になります。これを使って Python の

~~~python
{(x + i, y + j)
 for (x, y) in alives
 for i in range(-1, 2)
 for j in range(-1, 2)}
~~~

相当の関数を以下のように書くことができました:

~~~haskell
import Data.HashSet
import Data.List

territory_of (x, y) =
  (Data.HashSet.fromList
   $ concat [[(x + i, y + j) | i <- [-1..1]] | j <- [-1..1]])
~~~

最初、Python と同じような仕様だろうと思って `[ (x + i, y + j) | i <- [-1..1] | j <- [-1..1] ]` と書いてみたのですが、これだと直積集合にはなりません。

~~~haskell
*Main> [[(i, j) | i <- [-1..1] | j <- [-1..1]]]  ← NG
[[(-1,-1),(0,0),(1,1)]]
*Main> [[(i, j) | i <- [-1..1]] | j <- [-1..1]]  ← OK
[[(-1,-1),(0,-1),(1,-1)],[(-1,0),(0,0),(1,0)],[(-1,1),(0,1),(1,1)]]
~~~

※追記
実は以下のように書けば ParallelListComp 拡張は不要でした。コメント参照

~~~haskell
territory_of (x, y) =
  Data.HashSet.fromList [(x + i, y + j) | i <- [-1..1], j <- [-1..1]]
~~~

## ライフゲーム本体の記述

あとは OCaml とおなじノリでライフゲーム本体を以下のように書きました:

~~~haskell
neighbours_of (x, y) =
  Data.HashSet.delete (x, y) $ territory_of (x, y)

add_territory_set_of (x, y) set =
  Data.HashSet.union set $ territory_of (x, y)
territory_of_set set =
  Data.HashSet.foldr add_territory_set_of Data.HashSet.empty set

is_next_alive alives (x, y) =
  let increment_if_alive (x, y) c =
        if Data.HashSet.member (x, y) alives then (c + 1) else c in
    case Data.HashSet.foldr increment_if_alive 0 $ neighbours_of (x, y) of
      3 -> True
      2 -> Data.HashSet.member (x, y) alives
      _ -> False

life alives =
    let append_if_next_alive (x, y) new =
          if is_next_alive alives (x, y)
          then Data.HashSet.insert (x, y) new
          else new in
      Data.HashSet.foldr
        append_if_next_alive
        Data.HashSet.empty
        (territory_of_set alives)
~~~

心なしか、OCaml で書いたときより短くなったような気がします。
OCaml でプロトタイピングできた（経験を積んだ）ため、というのもありますし、OCaml に比べて書く必要があるおまじないが少ない気がしました。

※追記
fold を使わずに書けることに気が付きました。この方がわかりやすいと思います。

~~~haskell
neighbours_of (x, y) =
  Data.HashSet.delete (x, y)
  $ Data.HashSet.fromList [(x + i, y + j) | i <- [-1..1], j <- [-1..1]]

territory_of_set set =
  Data.HashSet.fromList
  $ [(x + i, y + j)
    | i <- [-1..1], j <- [-1..1],
      (x, y) <- Data.HashSet.toList set]

is_next_alive alives (x, y) =
  case
    Data.List.length
  $ Data.HashSet.toList
  $ Data.HashSet.intersection alives
  $ neighbours_of (x, y) of
    3 -> True
    2 -> Data.HashSet.member (x, y) alives
    _ -> False

life alives =
  Data.HashSet.fromList
  [(x, y)
  |(x, y) <- Data.HashSet.toList $ territory_of_set alives,
    is_next_alive alives (x, y)]
~~~

## 表示

OCaml のときと同様にグラフィック表示してみたかったのですが、さすがに Haskell 歴半日だと無理だったので断念しました。

仕方がないので、「生」状態を "*"、「死」状態を "." でテキスト表示する関数を作りました:

~~~haskell
print_life x0 y0 width height alives =
  let line_of x0 y width alives =
        (Data.List.foldr
          (\dx s -> if Data.HashSet.member (x0 + dx, y) alives
                    then "*" ++ s
                    else "." ++ s)
          ""
          [dx | dx <- [0..width]]) ++ "\n" in
    putStr (Data.List.foldr
             (\dy s -> (line_of x0 (y0 + height - dy) width alives) ++ s)
             ""
          [dy | dy <- [0..height]])
~~~

こんなものでもあるとないとは大違いです。

## テスト

上記のコードを、ファイル life.hs に書いておきます。

~~~sh
ghci -XParallelListComp
~~~

で ghci コマンドを立ち上げて（※ `-XParallelListComp` は不要でした。コメント参照）、ghci 上で `:load` で life.hs を読み込みます:

~~~
Prelude> :load life.hs
[1 of 1] Compiling Main             ( life.hs, interpreted )
Ok, one module loaded.
~~~

"グライダー" パターンを表示してみます。

~~~
*Main> p10 = print_life 0 0 10 10
*Main> p10 $ Data.HashSet.fromList [(0,2), (1,2), (2,2), (2,1), (1,0)]
...........
...........
...........
...........
...........
...........
...........
...........
***........
..*........
.*.........
~~~

関数 `life` で１ステップ進めたところを見るとこんなふうになります:

~~~
*Main> p10 $ life $ Data.HashSet.fromList [(0,2), (1,2), (2,2), (2,1), (1,0)]
...........
...........
...........
...........
...........
...........
...........
.*.........
.**........
*.*........
...........
~~~

関数 `life` 適用回数を増やしていくと、ステップが進んだときの状態を見ることができます:

~~~
*Main> p10 $ life $ life $ Data.HashSet.fromList [(0,2), (1,2), (2,2), (2,1), (1,0)]
...........
...........
...........
...........
...........
...........
...........
.**........
*.*........
..*........
...........
*Main> p10 $ life $ life $ life $ Data.HashSet.fromList [(0,2), (1,2), (2,2), (2,1), (1,0)]
...........
...........
...........
...........
...........
...........
...........
.**........
..**.......
.*.........
...........
*Main> p10 $ life $ life $ life $ life $ Data.HashSet.fromList [(0,2), (1,2), (2,2), (2,1), (1,0)]
...........
...........
...........
...........
...........
...........
...........
.***.......
...*.......
..*........
...........
*Main> 
~~~

## まとめ

- OCaml で書いたライフゲームを Haskell に直してみました。
- GHC のリスト内包表記拡張も Python のそれと同様に便利です。

GHC といえば Guarded Horn Clauses のことだ

と今まで食わず嫌いだったのですが、Haskell を勉強してみようかという気になってきました。