StateモナドをOCamlで実装してみるという不相応な事をやってみた

ずいぶんとエネルギーを持っていかれた気がする…

最近、モナドも使い慣れるといろいろ好都合だったりするので、自分用にほぼ最小に近いレベルでOCamlにモナドを実装していこうといろいろなモナドの実装をしています。とはいえ、まだMaybe, List, Lazyくらいですが。

そして今回、Stateモナドの実装をする事にしました。
多分大変だろうという予測はあったのですが、かなり大変でした。

最も参考になったサイトとしては
状態モナド遊び - http://d.hatena.ne.jp/kazu-yamamoto/20080604/1212573964
です。

Haskell知らないので、なんとなくこんな感じだろうという感じでしか読み取ってないので厳しいかったですが。

ちなみにコード的にはこんな感じ。
(2012/07/25 : 型を隠蔽する方向で書き換えました。基本的にはstate型の変更とrun関数の追加です)

module StateM : sig
  type ('a, 'b) state

  val bind : ('a, 'c) state -> ('a -> ('b, 'c) state) -> ('b, 'c) state
  val ( >>= ) : ('a, 'c) state -> ('a -> ('b, 'c) state) -> ('b, 'c) state
  val return : 'a -> ('a, 'b) state
  val get : ('a, 'a) state
  val put : 'a -> (unit, 'a) state
  val run : ('a, 'b) state -> 'b  -> ('a * 'b)
end = struct
  type ('a, 'b) state = 'b -> ('a * 'b)

  let bind m f = fun s -> let a, s' = m s in ((f a) s')
  let ( >>= ) = bind

  let return x = fun s -> (x, s)

  let get = fun s -> (s, s)
  let put s = fun _ -> ((), s)

  let run m a = m a
end

非常に最小限です。てか足りてるのかと言いたいくらい。

でもとりあえず使えなくはないみたいです。

次の例は「状態モナド遊び」の方でも書かれているリストのカウンター（大きさの保持）を上のコードでする場合の例です。
OCaml 3.12 以上じゃ無いと動きません。（local open使ってるので）

type 'a cons_list = Nils | Cons of 'a * 'a cons_list

let cons s lst =
  StateM.(get >>= fun i ->
    let i' = i + 1 in
    put i' >>= (fun x -> return (Cons (s, lst))))

(* リストに一個追加したら、カウンターが1になる *)
assert (Cons ("a", Nils), 1) = (StateM.(run (cons "a" Nils >>= fun s -> return s) 0))

(* リストに2個追加したら、カウンターが2になる *)
assert (Cons ("b", Cons ("a", Nils)), 2) = (StateM.(run (cons "a" Nils >>= cons "b" >>= fun s -> return s) 0))

正直、HaskellとOCamlの間をうろうろしつつ、型がどうなっているか、とかいろいろ考えているうちに頭がこんがらがっていました。ただ最終的にある程度理解を深める事ができたのが良かったです。

ちなみに参考にしたサイトとちょっと違うかなという点として、put関数は最終的に 'a -> (unit, 'a) state という型にしてあります。正直putの場合、('b, 'a) state のうちの 'b にあたる部分が不要なので unit にしてしまう事にしました。

あと最後に、実はStateモナドを作る際にFunctorにするかで悩んでいました。
簡単に言うと

module StateM (S : sig type s end) : sig
  type s = S.s
  type ('a, s) state = s -> ('a * s)

  ...
end = struct ... end

みたいにするかどうかです。
stateが持つ状態の型を先に決めてしまったモジュールを作るようにするかどうかってことですね。ただ、あまり利はなさそうだったというのと、Functorにしなくてもあまり害もなさそうなので多相にしてしまいました。

最後に追加してみたいかなと思ったのは、「状態モナド遊び」に書かれていた ( =<< ) という (>>=) の逆を行っている（であろう）演算子です。それを追加すると、例として書いたコードも少し変わって

assert (Cons ("a", Nils), 1) = (StateM.(run ((fun s -> return s) =<< cons "a" Nils) 0))

assert (Cons ("b", Cons ("a", Nils)), 2) = (StateM.(run ((fun s -> return s) =<< (cons "b" =<< cons "a" Nils)) 0))

のようにかけ（るはずなので）、Consの順番やリストの初期状態が一番右端に出てきてみやすいのでこれは入れるべきかも、と思いました。ただ結合順序的に、括弧が必要になるかもというのが厳しいところ。少しみやすくできるかもといったところですね。(Camlp4とか使えば、きっと優先順位を変えれるはず。でも、私の能力では到底不可能。せいぜい右結合な(^)や(@)を演算子の先頭にくっつける事しかできない;;)

以上、解説もない雑記でした。