2012-12-07

この記事は OCaml Advent Calendar 2012 の 7日目の記事です。

OCaml 3.12より導入され、4.00でさらに便利になった第一級モジュール (First-class modules)を使った小技を紹介します。ある種の単相的に定義された抽象データ型(ADT)を多相的にするという技です。 ~~(どこかで既出かも)~~

追記:

OCamlのテストスイートに良く似たコードがありました。
Higher Order Fun by MATÍAS GIOVANNINI では、似た技でモナドを表現しています。 @osiire と @camloeba 両氏のつぶやきも参考になります。 (thanks to @camloeba さん)
「Haskell では…なのに」 → 次の日のエントリを見て下さい

OCamlのStdlibのSetモジュールは、多相的ではありません。ここで多相的でないとは、集合の型が型パラメータを取らないことを言っています。例えば、Setを使う場合は Functorに比較関数を与え、集合の型に特化したモジュールを合成するのですが、

(* int用の順序 *)
module IntOrd = struct
  type t = int
  let compare = Pervasives.compare
end

(* intの集合のモジュール *)
module IntSet = Set.Make (IntOrd)

ここで合成された IntSet モジュールは、例えば add : int -> IntSet.t -> IntSet.t のように、集合の要素が IntSet.t という単相型になっています。つまり、様々な型の値の集合に対する操作を与えたい場合、お好みのSetモジュールを返すような別なFunctorを作ることになります。

本来、多相的に扱えそうなSetが、単相的になってしまう…モヤモヤしますね…

そこで、この単相的なSetを、OCaml3.12より導入されたFirst-class modules (第一級モジュール)を使い、多相的なSetにする方法を紹介します。

(Setモジュールが多相でない理由は、二項演算を効率よく実装するためだと考えられます。たとえば和集合を計算する場合、二つの木を連結する操作が必要になりますが、効率よく木を連結するにはそれぞれの木の順序付けが同一である必要があります。もし次の方法で集合を多相にした場合、引数に渡された二つの集合の順序付けが同じであることを保証できないため、和集合は一方に他方の要素を1つずつ追加して計算することになります。こればっかりはどうしようもありませんので、そのような効率は犠牲にすることにします。Batteriesには多相な集合を扱うPSetというモジュールもあります。追記: @garriguejej さんのコメントも参照)

モジュールのシグネチャ

type 'a t
(*空集合: 比較関数を与える*)
val empty : ('a -> 'a -> bool) -> 'a t
val is_empty : 'a t -> bool
val mem : 'a -> 'a t -> bool
val add : 'a -> 'a t -> 'a t
val singleton : ('a -> 'a -> bool) -> 'a -> 'a t
val remove : 'a -> 'a t -> 'a t
(* ... *)

普通の集合演算ですが、Functor版と異なり、集合を作る時に比較関数を決められるところが違います。

モジュールの実装

追記：@garriguejej さんによるコメントも参照

(* 1st class moduleに、モジュールとその値を包むための型 *)
module type MySet = sig
  module S : Set.S
  val set : S.t
end

(* 多相的な集合の型! First-class moduleを使い、要素の型はモジュール制約で多相に *)
type 'a t = (module MySet with type S.elt = 'a)

(*空集合をつくる. *)
(*(type s) は型束縛(locally abstract types)の構文であり、引数ではない.  empty:('a -> 'a -> bool) -> 'a t *)
let empty (type s) (cmp : s -> s -> int) : s t = 
  (* 比較関数から、ローカルモジュールとそのモジュールの空集合をつくる *)
  let module M = struct
    module S = Set.Make (struct type t = s let compare = cmp end)
    let set = S.empty
  end 
  in (module M : MySet with type S.elt = s) (* ローカルモジュールを1st-class module の値に *)

(*空集合か否か*)
(* is_empty (m:'a t) と書きたいところだが、1st-class moduleの型推論に関わるので、こう書く必要がある *)
(* これで is_empty の型はちゃんと 'a t -> bool になる *)
let is_empty (type s) (m:s t) = 
  let module M = (val m) in (* 1st-class module を開く*)
  M.S.is_empty M.set

let mem (type s) (v:s) (m:s t) = 
  let module M = (val m) in
  M.S.mem v M.set

let add (type s) (v:s) (m:s t) : s t = 
  let module M = (val m) in
  let module M' = struct (* 別のモジュールを作る *)
    module S = M.S
    let set = M.S.add v (M.set)
  end in (module M' : MySet with type S.elt = s)

(*...*)

まとめ

First-class moduleの使い道のひとつを紹介しました。ポイントは、単相なものから多相性を復活させる

type 'a t = (module MySet with type S.elt = 'a)

なる書き方ができることで、これはなかなか興味深いですね。

他にも色んなテクニックがありますので、皆さんもOCamlと第一級モジュールの世界をぜひ探検してみてください!

keigoiの日記

第一級モジュールでSetの多相性を復活させてみよう

モジュールのシグネチャ

モジュールの実装

まとめ