OCamlでモナドっぽいものを作る

ライブラリの拡充と関数型言語のお勉強を兼ねて、モナドっぽいものを実装して見ました。
単純にモナドをOCamlで使いたいだけならMonad拡張を入れる方が手っ取り早いですが、あまり外部ライブラリへの依存性を入れたくないのと、OCamlの記法の中だけでどこまで出来るか試してみたかったので。
ちなみに誤解を避けるため先に断っておきますが、自分はHaskellerではありません。
以下ではモナドに関してHaskellをかなり参考にしていますが、Haskellのモナドに対する勘違いなどが含まれている可能性があります。
ご了承下さい。

とりあえず、インターフェースとなるシグネチャから作っていきます。

(* 型付きモナドのシグネチャ *)
module type TypedMonadType =
sig
  type 'a t
  val empty : 'a t
  val singleton : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end
(* 型付きモナドの実装強化 *)
module TypedMonad(S:TypedMonadType) =
struct
  open S
  let (>>=) = bind
  let (=<<) f m = m >>= f
  let fail = empty
  let return = singleton
  let rec sequence x = function
      [] -> x
    | f::t -> sequence (x >>= f) t
  let sequence_ m l = sequence m l; ()
end

型付きモナドって書くと、型なしモナドがあるのか、という話になりますが、Set.tなどは型がeltとして別に定義されるためそっちをMonadとして、optionやlistのように型が’a tになるものを型付き、としています。
……多相とか考えると逆な気もしますが、まぁ記述を中心に捉えると型’aが付いてるよね、ということで。

さて、TypedMonadTypeシグネチャでは最低限の実装、モナドの型’a tとempty、singleton、bindを定義しています。
Haskellでいうとemptyがfail、singletonがreturn、bindが>>=ですね。
このへんの名前はOCamlのSet.Sのネーミングに合わせています。
TypedMonadファンクタではこのシグネチャに適合するストラクチャを受け取り、これらの複合関数を定義します。
一応、Haskellでの名前も、ファンクタで別名として定義してます。

では、このファンクタを利用してOptionモナドを作ってみましょう。
ユーティリティのため、モナドと関係ない関数もいくつか定義しています。

module Option =
struct
  (* 中核となるモジュール *)
  module Core =
  struct
    type 'a t = 'a option
    let compare = compare
    let empty = None
    let singleton x = Some x
    let add x _ = Some x
    let bind x f =
      match x with
      None -> None
    | Some x -> f x
    let to_list = function
    None -> []
      | Some x -> [x]
    let fold f x e =
      match x with
      None -> e
    | Some x -> f x e
  end
  (* 中核と、それを元にした拡張を実装 *)
  include Core
  include TypedOrdered(Core)
  include TypedMonad(Core)
  include TypedCollection(Core)
end

bindはxがNoneならNoneのまま、Some xならf xを返します。
HaskellのMaybeモナドの定義そのままですね。
TypedMonadにストラクチャを渡す必要があるので、中核となる部分を一度Coreモジュールとして定義し、そのままincludeしています。
Coreが外部からも見えてしまいますが、気持ち悪い場合はシグネチャを書けばよいかと。
TypedOrderedとかTypedCollectionとかはTypedMonadと同じく、Coreを受け取って複合関数を定義します。
TypedOrderedならequalや前回記事にしたfix、TypedCollectionならof_listやto_listなどが自動で定義されますが、その辺は次回に。

さて、これで準備はOKです。
対話環境でちゃんと使えるか試してみます。

# let div2 x = if x mod 2 = 1 then None else Some (x / 2);;
val div2 : int -> int option = <fun>
# let open Option in
    Some 8 >>= div2 >>= div2;;
- : int Option.Core.t = Some 2
# let open Option in
    Some 7 >>= div2 >>= div2;;
- : int Option.Core.t = None
# let open Option in
    Some 2 >>= div2 >>= div2;;
- : int Option.Core.t = None

かなり作為的な例ですが、div2はxが奇数ならNone、偶数なら2で割った値を返します。
つまり、2で割って小数になるような場合はNoneになります。
strict_div2とかの方が適切かもしれません。
例を見ると、8は2で割って4、更に2で割って2なので、Some 2になります。
一方7は2で割ると3.5なので小数になります。この場合、結果はNoneです。
また2も、2で割ると1で、更に2で割ると0.5、こちらも小数なのでNoneです。
上手いこと動いていますね。

bind関数を繰り返すときにいちいちOption.bindと書くのは面倒なので、局所オープン記法を使っています。
これにより、中置記法が使えるのでとても便利です。
ちなみにopenしないとモジュール内に定義された中置記法を中置で使うことはできないようです。
Option.(>>=)として参照することは出来ますが、この場合前置記法になるためOption.bindと等価になります。

あと、局所オープン記法は以下のようにすることもできます。

# Option.(Some 4 >>= div2 >>= div2);;
- : int Option.Core.t = Some 1

短い式ならこちらのほうがわかりやすいですね。
ただ括弧が増えるので、好みによるところでしょうか。

さて、次はListモナドです。

module List =
struct
  module Core =
  struct
    include List
    type 'a t = 'a list
    let compare = compare
    let empty = []
    let singleton x = [x]
    let cons x l = x::l
    let add = cons
    let bind l f = flatten (map f l)
    let fold f l e =
      fold_left (fun m e -> f e m) e l
  end
  include Core
  include TypedOrdered(Core)
  include TypedMonad(Core)
  include TypedCollection(Core)
end

こちらも色々と独自拡張を施してますが……まぁさっきと似たような感じです。
emptyが空リスト、singletonが要素1つのリスト、そしてbindはfをmapしてflattenします。
この辺もHaskellのリストモナドまんまですね。

対話環境で試してみます。

# List.([3;1;4] >>= fun x -> [x;x*2;x*3]);;
- : int List.Core.t = [3; 6; 9; 1; 2; 3; 4; 8; 12]
# List.([3;1;4] >>= fun x -> [x;x*2;x*3] >>= fun x -> [x;x+1]);;
- : int List.Core.t =
[3; 4; 6; 7; 9; 10; 1; 2; 2; 3; 3; 4; 4; 5; 8; 9; 12; 13]

例を考えるのが面倒だったので、IT Proの例をそのままお借りしました。
最初の例ではリストに対し、それぞれの要素の自身、2倍、3倍を並べたようなものを構成しています。
2番目の例では最初の例の操作をした上で、更に各要素の自身、+1したものを並べています。
……あんまりありがたみが感じられないですね。
もっと有用な例がありそうですが、そういう例は大体do記法とかguardとか使ってかっこいい感じのことをやっていて、現状の実装では試せない例が多いんですよねぇ。
ま、そういうのがやりたい人は拡張を（ｒｙ

さて、上のListモナドを見ると、いわゆる並行計算的なことをしているイメージが持てると思います。
実際参考にしたモナドのすべてでも、「非決定性をもつ計算の連鎖を、演算をそれぞれのステップで 可能なすべての値に適用することで、合成する戦略」などと記載されています。
このイメージは大変良くわかるのですが、気になるポイントとして、重複する要素はまとめたほうが効率良さそうじゃないですか？
上の2つ目の例では2、3、4が重複していますが、重複度を必要としない場合、ここから計算の連鎖が続くのは無駄なわけです。
となると、そういう場合はListよりSetのほうが便利なんじゃないでしょうか。

ということで、Setを拡張してSetモナドを作ってみます。
こちらは要素の型と集合の型が分かれているので、それに合わせたMonadTypeとかを定義していきます。

(* モナドのシグネチャ *)
module type MonadType =
sig
  type elt
  type t
  val empty : t
  val singleton : elt -> t
  val bind : t -> (elt -> t) -> t
end
(* モナドの実装強化 *)
module Monad(S:MonadType) =
struct
  open S
  let (>>=) = bind
  let (=<<) f m = m >>= f
  let fail = empty
  let return = singleton
  let rec sequence x = function
      [] -> x
    | f::t -> sequence (x >>= f) t
  let sequence_ m l = sequence m l; ()
end
(* 集合モジュール *)
module Set =
struct
  (* 集合モナドの生成ファンクタ *)
  module Make(S:OrderedType) =
  struct
    (* 中核部 *)
    module Core =
    struct
      include Set.Make(S)
      let bind s f = fold (f >> union) s empty
      let bind_reflect s f = fold (f >> union) s s
      let closure f s =
    fix (fun x -> bind x f) s
      let closure_reflect f s =
    fix (fun x -> bind_reflect x f) s
    end
    (* 実装と拡張 *)
    include Core
    include Ordered(Core)
    include Monad(Core)
    include Collection(Core)
  end
end

めんどいのでSとかは省いています。
実用上はないとまずいんですけどね。

集合の場合は、empty、singletonはそのままです。
こちらに合わせて名前を決めたので当然ですね。
bindは、fを各要素に適用した後、unionを取ります。
意味合いとしてはmapしてから全体のunionを取るのでListの場合と同じですが、Setの場合は型の都合上mapができないのでこのような形になります。
ちなみに同じく型の都合上、intからfloatの集合にするようなことはできません。
このへんはListの方がフレキシブルですね。

さて、こちらも対話環境で試してみます。
ちなみにto_listやof_listはCollectionで定義しています。

 
# module IntSet = Set.Make(Int);;
module IntSet :
...
  end
# IntSet.(of_list[3;1;4] >>= (fun x -> of_list[x;x*2;x*3]) |> to_list  );;
- : IntSet.Core.elt list = [1; 2; 3; 4; 6; 8; 9; 12]
# IntSet.(of_list[3;1;4] >>= (fun x -> of_list[x;x*2;x*3])
   >>= (fun x -> of_list[x;x*2]) |> to_list);;
- : IntSet.Core.elt list = [1; 2; 3; 4; 6; 8; 9; 12; 16; 18; 24]

Listモナドと同じようなものを書いてみました。
ちなみに|>はfunの->より結合が強いので、括弧をなくすと結合順が変わってエラーになります。
出力を見てもらうと、先ほど重複してた要素の重複がなくなりました(ま、集合なので当然ですが)。

とりあえず今のところはこんなところです。
MonadPlusとかguardとかmapMとか色々勉強したいところですが、あんまり凝り過ぎるとOCamlとして読めないプログラムになりそうなのでモナドはとりあえずこの辺までにしとこうかと思います。(もうOCamlじゃないってツッコミが聞こえそうですが)
そもそも、Optionモナドが便利そうなので試してみたかっただけなんですが、やけに大掛かりになってしまいました。

当然ながら、言語としてサポートされていない以上真似事にすぎないので、まじめにモナドを使いたい場合はHaskellやるなりOCaml拡張入れるなりF#使うなりするのがいいかと思います。
見てもらえば分かる通りF#使いたいんですけどね……研究終わるまではOCaml縛りです。

別にOCamlが嫌いってわけではなくむしろ好きなんですが、標準ライブラリが弱すぎるのが（ｒｙ
CoreとかBattery使うのも今更感が漂いますし、これまで作ったのを新しいライブラリに合わせて書き換えるのも手間なので、標準ライブラリと互換性を持たせて拡張してます。
Monadもその一環で、見てもらえば分かる通りOrderedとかCollectionとかいろいろ弄ってます。
今度その辺についてもまとめておきたいところです。