OCaml でライフゲーム

## 動機

手続き型言語はだめだ、関数型言語えらい、というような言説を最近あまり見かけなくなった気がしますが、それでもたまに「関数型の方がいいのかなあ」と思えることもあります。

そんなわけで勉強がてらに、 [以前 Python で書いたライフゲーム](https://qiita.com/tadashi9e/items/370bcb3c1028700201c1) を OCaml で書き直してみます。

## Life 1.05 形式ファイルの読み込み

初期状態をハードコードするのは面倒なので、 [Life 1.05 形式のファイル](https://qiita.com/tadashi9e/items/b2ff031dd17172d5bb39) を読み込めるようにしてみます。

Life 1.05 形式のファイルは以下のようなものです:

~~~
#Life 1.05

***
..*
.*.
~~~

方針としては、一旦ファイル全体を行単位で区切られた文字列のリストとして取り込み、各行について '*' を「生」状態セル、それ以外を「死」状態セルとみなしてパースしていくことにします。'#' 以降はコメントとして読み飛ばします。
「生」状態セルの座標を (x, y) 形式のペアとしてそのリストとしてパース結果を返します。

~~~ocaml
(*
 関数 input_line_crlf:
 CRLF 形式に対応した input_line

 引数: f, in_channel
 戻り値: string
 *)
let input_line_crlf chan =
  let rec foreach_char s =
    let c = input_char chan in
    match Char.code(c) with
      0x0a -> s
    | 0x0d -> foreach_char s
    | _ -> foreach_char (s ^ (String.make 1 c))
  in
  foreach_char ""

(*
 関数 load105_from:
 LIFE1.05 形式のファイルを読み込む。

 引数: (x, y), int * int.
       file_name, string.
 戻り値: ('a * 'b) list
 *)
let load_life105_from (x, y) file_name =
  (* 行文字列を解釈する *)
  let parse_105_line (x, y) line points =
    let rec line_points_of_offset dx lst =
      if dx < String.length line then
        match String.get line dx with
          '#' -> lst
        | '*' -> (x + dx, y) :: line_points_of_offset (dx + 1) lst
        | _ -> line_points_of_offset (dx + 1) lst
      else
        lst
    in
    line_points_of_offset 0 points
  in
  (* 行文字列のリストを LIFE1.05 形式とみなして解釈する *)
  let parse_105_lines (x, y) lines =
    let rec points_of_offset dy lst = function
        [] -> lst
      | line::rest ->
        points_of_offset (dy + 1) (parse_105_line (x, y + dy) line lst) rest
    in
    points_of_offset 0 [] lines
  in
  (* ファイルを行文字列のリストとして読み込む手続き *)
  let lines = ref [] in
  let chan = open_in file_name in (
    try
      while true do
        let line = input_line_crlf chan in
        print_endline line;
        lines := line :: !lines
      done;
    with End_of_file ->
      close_in chan);
  (* 読み込んだ行文字列のリストを「生」位置のリストとして返す *)
  parse_105_lines (x, y) !lines
~~~

ここで、input_line_crlf は CRLF 改行コードに対応させた input_line 互換関数です。
Life 1.05 ファイルは CRLF 改行コードを用いることになっていますが、CRLF 改行コードのファイルは input_line で取り扱うことができませんでした。
読み込むファイルの改行コードを書き換えてもよかったのですが、比較的簡単に input_line 互換関数が書けたのでこれを用いることにしました。

## ライフゲーム本体

Python でのライフゲームは以下のように書けます。

~~~python
def life(alives):
    u'''ライフゲームのルールに従って、与えられた「生」セルの座標 set を元に
    次のステップの「生」セルの座標 set を返す。
    --------
    alives: Set[Tuple[int, int]]
        「生」セルの座標の set

    Returns
    --------
    next_alives: Set[Tuple[int, int]]
        次のステップでの「生」セルの座標の set
    '''
    return {point
            for point, n in collections.Counter([(x + i, y + j)
                                                 for (x, y) in alives
                                                 for i in range(-1, 2)
                                                 for j in range(-1, 2)
                                                 if i != 0 or j != 0]).items()
            if n == 3 or (n == 2 and point in alives)}
~~~

なるべくこのまま OCaml に持っていきたいところなのですが、当方の OCaml 力不足もあって、こんなに簡単には書けませんでした。

### 「生」状態セル集合

Python 実装では、「生」状態セルの集合の検索コストを抑えるために Set を用いています。
同様に、OCaml でも (x, y) を格納できるハッシュセットを準備しておきます:

~~~ocaml
module Position =
  struct
    type t = int * int
    let equal (x0,y0) (x1, y1) =
      match Stdlib.compare x0 x1 with
        0 -> if Stdlib.compare y0 y1 = 0 then
          true else false
      | c -> false
    let hash (x, y) = x * 1023 + y
  end

module PositionSet = Hashset.Make(Position)
~~~

動作確認用、あるいはユーティリティ関数として以下も作りました:

~~~ocaml
(*
 関数: create_position_set_of:
 与えられたリストに対応する PositionSet を返す。

 引数: position_list, (int * int) list.
 戻り値: PositionSet.t
 *)
let create_position_set_of position_list =
  List.fold_left
    (fun s p -> PositionSet.add s p; s)
    (PositionSet.create (List.length position_list))
    position_list

(*
 関数: print_position_set:
 与えられた PositionSet の内容を表示する（デバッグ用）。

 引数: PositionSet.t
 戻り値: なし
 *)
let print_position_set set =
  PositionSet.iter (fun (x, y) ->
    print_string "(" ; print_int x ; print_string "," ;
    print_int y ; print_string ") ")
    set
~~~

### テリトリ

ここでは、あたえられた「生」状態セル座標点に対して、次ステップで状態変化の可能性のあるセル座標点の集合を「テリトリ」と呼ぶことにします。

Python では、現在の「生」状態セルについてのテリトリを以下で得ることができます:

~~~python
# 座標点 (x, y) に対応するテリトリを構成する座標点のリスト
[(x + i, y + j)
 for i in range(-1, 2)
 for j in range(-1, 2)]
~~~

~~~python
# 座標点の集合 alives に対応するテリトリを構成する座標点の集合
{(x + i, y + j)
 for (x, y) in alives
 for i in range(-1, 2)
 for j in range(-1, 2)}
~~~

これに相当する関数を OCaml で書きました：

~~~ocaml
(*
 関数 territory_list_of:
 与えられた点 (x, y) について、テリトリを構成する点のリストを返す。

 引数: (x, y), int * int.
 戻り値: (int * int) list.
 *)
let territory_list_of (x, y) =
  (* x のリストと y のリストを元に、(x, y) の全組み合わせ（直積集合）を作る *)
  let product xs ys =
    List.fold_left (fun a x -> (List.map (fun y -> (x, y)) ys) @ a) [] xs
  in
  (* x + a から x + b までの値のリストを作る *)
  let range a b x = List.init (b - a + 1) (fun i -> i + a + x) in
  (* x-1, x, x+1 と y-1, y, y+1 の位置のリストを返す *)
  product (range (-1) 1 x) (range (-1) 1 y)

(*
 関数 territory_set_of
 与えられた点すべてのテリトリを構成する点の集合を返す。

 引数: set, PositionSet.t
 戻り値: PositionSet.t
 *)
let territory_set_of set =
  (* position のテリトリを set に追加する *)
  let add_territory_of position set2 =
    List.fold_left
      (fun s p -> PositionSet.add s p; s)
      set2
      (territory_list_of position)
  in
  (* set の全テリトリを返す *)
  PositionSet.fold
    add_territory_of
    set
    (PositionSet.create (PositionSet.cardinal set))
~~~

### 隣接生存セルの数え上げと、次ステップセル状態の決定

次ステップで変更の可能性がある場所（テリトリ）内の点について、次ステップの生死を判定する必要があります。
生死の判定は隣接セルにどれだけ「生」状態セルが存在するかで決まります。

~~~ocaml
(*
 関数 is_next_alive:
 与えられた点 position の次ステップの状態が「生」なら true を、
 「死」なら false を返す。

 引数: position, int * int.
       set, PositionSet.t
 戻り値: bool
 *)
let is_next_alive position set =
  (* 与えられた点 (x, y) に隣接する「生」セルのリストを得る *)
  let neighbours_list_of (x, y) =
    List.filter
      (fun (x0, y0) -> x0 != x || y0 != y)
      (territory_list_of (x, y))
  in
  (* 与えられた点 position に隣接する「生」セルを数える *)
  let count_neighbours position set =
    List.fold_left
      (fun c p -> if PositionSet.mem set p then (c + 1) else c)
      0
      (neighbours_list_of position)
  in
  (* LIFE のルールに従って次ステップでの生死を決定する *)
  match count_neighbours position set with
    3 -> true
  | 2 -> PositionSet.mem set position
  | _ -> false
~~~

### 空間全体の次ステップセル状態の決定

ここまでの関数を使って、ライフゲーム本体を以下のように書くことができます:

~~~ocaml
(*
 関数 life:
 与えられた「生」状態セル座標の集合 set を元に、
 次ステップでの「生」状態セル座標の集合を返す。

 引数: alives, PositionSet.t
 戻り値: PositionSet.t
 *)
let life alives =
  (* 次ステップで変動する可能性のあるセル *)
  let territory_set = territory_set_of alives in
  let territory_list =
    PositionSet.fold (fun p s -> p :: s) territory_set [] in
  (* 次ステップのセル状態の決定 *)
  List.fold_left
    (fun s p -> if is_next_alive p alives then (PositionSet.add s p; s) else s)
    (PositionSet.create (PositionSet.cardinal territory_set))
    territory_list
~~~

## グラフィック表示

与えられた「生」状態セル座標の集合を Graphics 上に描画する関数を作りました:

~~~ocaml
module G = Graphics

(*
 関数 update_display:
 グラフィック上に apixel_size の大きさの点を描画する。
 左下の点の位置を原点 (x0, y0) とする。

 引数: pixel_size, int.
       (x0, y0), int * int.
       set, PositionSet.t
 戻り値: なし
 *)
let update_display pixel_size (x0, y0) set =
  G.set_color (G.rgb 0 0 0);
  G.fill_rect 0 0 (G.size_x ()) (G.size_y ());
  G.set_color (G.rgb 255 255 255);
  PositionSet.fold
    (fun (x, y) () -> G.fill_rect
        (x0 + x * pixel_size) (y0 + y * pixel_size) pixel_size pixel_size)
    set ();
  ()
~~~

予め `G.open_graph " 300x300"` などで適当な大きさのウィンドウを開いておいてから update_display を呼び出すと、そのウィンドウ上に描画します。

## テスト

graphics.cma, hashset.cma が必要です。

当方の場合、opam install graphics や opam install hashset でライブラリを導入しました。

そのうえで、以下のようにライブラリをロードした状態で utop を起動しました:

~~~sh
utop -I $(ocamlfind query graphics) graphics.cma -I $(ocamlfind query hashset) hashset.cma
~~~

ここまでの OCaml コードを、ファイル "life.ml" に書いておくと、utop で以下のようにライフゲームを実行することができます:

~~~ocaml
#use "life.ml";;

G.open_graph " 300x300" ;;

let s0 = create_position_set_of (load_life105_from (200, 200) "acorn.life") in
let s = ref s0 in
for step = 1 to 1000 do
  let s2 = life !s in
  update_display 1 (0, 0) s2;
  s := s2;
  Unix.sleepf 0.0001;
done;;
~~~

load_life105_from に指定する初期ロード位置、update_display に与える表示サイズ、表示位置などは適宜調整が必要です。

## まとめ

* OCaml の Hashset を使ってライフゲームを書いてみました。
* OCaml でのグラフィック描画は手軽にできます。
* Python のリスト内包表記の便利さを再認識しました。

## 追記

記事中のソースコードにはタイプミスが含まれることがあるので、手元で実行してみたい方は以下をご利用頂いたほうが安全です：

https://github.com/tadashi9e/life_game_in_ocaml