第一級モジュールでジェネリックなSet操作

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

昨日のエントリでは無理矢理 'a t の形で扱える Setモジュールを作りましたが、これには欠点があり、 'a t型をもつ各集合で、'aの同値性の付け方が異なってしまいます。 昨日の記事に @garriguejej さんがコメントしたとおり、Setモジュールのバイナリメソッドunionやdiffなどは（各引数で'aの同値性が異なるかもしれず）使えないのです。
結局、集合の表現が 'a について同じ同値性をもつことを型で強制するには、Set.Makeをそのまま使うべき、ということですね。

では様々なSetについてジェネリックな関数はOCamlで書けないのでしょうか？ そんなことはないです。第一級モジュールがあればできます。

例

(* Setモジュールを第一級に *)
type ('t,'elt) set = (module Set.S with type t = 't and type elt = 'elt)

(* 
  多相なSet操作関数: 第一引数にどのSetに対する操作か指定する 
*)

(*
  val empty : ('a, 'b) set -> 'a
あるいは
  val empty : (module Set.S with type t = 'a and type elt = 'b) -> 'a
*)
let empty (type t) (type elt) ((module S) : (t,elt) set) = 
  S.empty

(*
  val add : ('a, 'b) set -> 'b -> 'a -> 'a
あるいは
  val add : (module Set.S with type t = 'a and type elt = 'b) -> 'b -> 'a -> 'a
*)
let add (type t) (type elt) ((module S) : (t,elt) set) =
  S.add

let singleton (type t) (type elt) ((module S) : (t,elt) set) =
  S.singleton

(* バイナリメソッドも定義できる *)
let union (type t) (type elt) ((module S) : (t,elt) set) =
  S.union

(* int,string の標準的な集合 *)
module IntSet = Set.Make (struct type t=int let compare = Pervasives.compare end)
module StrSet = Set.Make (struct type t=string let compare = Pervasives.compare end)

(* 比較関数が異なるIntSet *)
module IntSet2 = Set.Make (struct type t=int let compare x y = compare y x end)

let int : (IntSet.t,int) set = (module IntSet)
let int2 : (IntSet2.t,int) set = (module IntSet2)
let string : (StrSet.t,string) set = (module StrSet)

(* 
  使ってみよう
*)

let ia = singleton int 1
let ib = singleton int 2
let iab = union int ib ib

let sa = singleton string "a"
let sb = singleton string "b"
let sab = union string sa sb

(* 比較関数が異なると型エラー *)
let ic = singleton int2 3
(*
let iac = union int2 ia ic
Error: This expression has type IntSet.t
       but an expression was expected of type IntSet2.t
*)

これってどういうこと？

OCaml 3.11までは、Setについて多相な関数群を書く場合

module MySet(S:Set) = struct
  let empty = S.empty
end

と書いてSetモジュールを引数に取るfunctorを書いていたところを、

let empty (type t) (type elt) (module S : Set.S with type t = t and type elt = elt) = S.empty

などと、関数ごとにSetモジュールを受け取るように書き換えたのでした。 これが型の省略により

let empty (type t) (type elt) ((module S) : (t,elt) set) = S.empty

という記法になっているというお話です。
つまるところやってることはあまりfunctorと変わらないので、ここまでやるなら 素直にfunctor を使ったほうがいいかもしれませんね。

Haskell や Scala との比較

ところで

singleton int 1

のintは第一級モジュールの値を渡しているのですが、これは 型intの時に何をすべきかというディスパッチが書かれた辞書を渡しているようなものです。Haskellの型クラスで (Set s => Int -> s Int) 等と書くと、型推論により唯一のSetのインスタンスが決まるので暗黙にこのような辞書が渡されます。 Scalaなら implicit parameterで渡せますね。

この技が使えないとき

この方法は、 t や elt の型が 型引数を取る 'a t や 'a elt になった場合、破綻します。 たとえば モナドはこの方法では駄目で、詳しくは昨日のエントリからリンクした記事を読んでみてください。