OCamlでSetをmapする関数

2011-11-30 プログラミング

今日も今日とてOCamlでプログラムをガリガリ書いていたのですが、どうしても気になってSetをmapする関数を作って見ました。
とはいえ、さすがにSetに組み込むのは無理なので、外部で似たようなことをやるための汎用関数ですが。

let mapper folder adder empty f s =
  folder (f >> adder) s empty

こんな感じです。

以下のように、元Setのfold関数や先Setのadd、emptyを与えて使います。

module Int =
  struct
    type t = int
    let compare = compare
  end
module Float =
  struct
    type t = float
    let compare = compare
  end
module IntSet =
  Set.Make (Int)
module FloatSet =
  Set.Make (Float)
(* IntSetからFloatSetへのmap *)
let setmap_itof =
  mapper IntSet.fold FloatSet.add FloatSet.empty
(* FloatSetからIntSetへのmap *)
let setmap_ftoi =
  mapper FloatSet.fold IntSet.add IntSet.empty

ちなみに、単にfoldの結合を隠蔽しているだけなので、mapでも使えます。
一瞬型が合うか不安になりますが、foldの引数とaddの引数を考えるとうまく対応しています。

module IntMap = Map.Make (Int)
module FloatMap = Map.Make (Float)
(* IntMapからFloatMapへのmap *)
let mapmap_itof =
  mapper IntMap.fold FloatMap.add FloatMap.empty
(* FloatMapからIntMapへのmap *)
let mapmap_ftoi =
  mapper FloatMap.fold IntMap.add IntMap.empty

実はListからSetへの変換も簡単に作れます。
この場合はfが不要なので、自分自身を返すid関数を渡してやります。

let id x = x
let iset_of_list =
  mapper List.fold_right IntSet.add IntSet.empty id

ちゃんと動作するか確認してみましょう。
以下の例は、10以下の奇数のリストを集合にした後、この集合の平方根を持つ集合へと変換します。

# let s1 = iset_of_list [1;3;5;7];;
val s1 : IntSet.t = 
# let s2 = setmap_itof (float_of_int >> sqrt) s1;;
val s2 : FloatSet.t = 
# FloatSet.elements s2;;
- : FloatSet.elt list =
[1.; 1.73205080756887719; 2.23606797749979; 2.64575131106459072]

うまく動作しているようです。
ただし、この関数だけではタプルのリストからMapへ変換したり、SetからMapに変換したり、あるいはMapのkeyだけを取り出したSetを作ったり、といったことは出来ません。
先ほどMapのmapが作れたのは上手いこと1引数関数に見なせたからで、基本的には’a -> ‘bによる写像でないと動かないわけですね。

さて、よくよく上の例を見ると、実はSetとかListとかいった構造はあまり関係なくて、要するに以下のシグネチャを満たすモジュールであれば上の関数を適用できそうです。

module type S =
  sig
    type elt
    type t
    val empty : t
    val add : elt -> t -> t
    val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
  end

ということはファンクター使えば上手いことaddとかfoldを考えず関数を作れそう……に思いますが、残念なことに、ファンクターは「ストラクチャーを受け取ってストラクチャーを返す」機構のため、「ストラクチャーを受け取って関数を返す」ということは、言語仕様上出来ません。

(* こんなのはできない *)
let mapper =
  functor (S1 : S) ->
    functor (S2 : S) ->
      fun f s ->
        S1.fold (f >> S2.add) s S2.empty

ただし、勘違いしていたのですが「ファンクターのファンクター」は作れるみたいです。
というわけで、相互にmapを行うMapperは以下のようにして作ることができます。

module Mapper(S1:S)(S2:S) =
  struct
    let map f s =
      S1.fold (f >> S2.add) s S2.empty
    let remap f s =
      S2.fold (f >> S1.add) s S1.empty
  end

で、これを使うに当たって問題がひとつ。
ListはSと全然適合しない型になっています。
まぁ、この型を持たせようと思うとListがファンクターになってしまうので仕方ないのですが。
というわけで、Sに適合するIntListを作っておきます。

(* Listの型を指定するためのシグネチャ *)
module type Type =
  sig
    type t
  end
(* リストのファンクタ *)
module AbstructList(S:Type) =
  struct
    type elt = S.t
    type t = elt list
    let empty = []
    let add x l = x::l
    let fold = List.fold_right
  end
(* int型のリスト *)
module IntList =
  AbstructList(Int)
(* IntListからIntSetへのMapper *)
module IListIsetMapper =
  Mapper(IntList)(IntSet)
(* IntSetからFloatSetへのMapper *)
module ISetFSetMapper =
  Mapper(IntSet)(FloatSet)

ようやく準備が出来ました。
先ほどと同じことを試してみます。

# let s1 = IListISetMapper.map id [1;3;5;7];;
val s1 : IntSet.t = 
# let s2 = ISetFSetMapper.map (float_of_int >> sqrt) s1;;
val s2 : FloatSet.t = 
# FloatSet.elements s2;;
- : FloatSet.elt list =
[1.; 1.73205080756887719; 2.23606797749979; 2.64575131106459072]

うまくいきました。が、いかんせん関数呼び出しが長いです。
実際には、以下のように各モジュールの関数を短い名前で再定義して使うべきでしょうね。

let map_ltoi = IListISetMapper.map
let map_itof = ISetFSetMapper.map

というわけで、思ったより長くなりましたが、Setをmapする方法として、以下の二種類の方法を紹介しました。

fold、add、emptyを取る関数を作る
- 2つのモジュールを取るファンクターを作る
1つ目の方は実質的にはfoldに制約を加えたものに近いですが、使い所は結構多いんじゃないでしょうか。
2つ目の方も、map関数だけだと微妙ですが色々な相互関数を入れればユーティリティとして使えそうな予感がします。
……ま、こんな物を作る必要がある時点で、OCamlのモジュールシステムがこういった面で不便である、ということな気もしますが。

むしろ今回一番の収穫は、ファンクターのファンクターでも省略記法が使えることがわかった、というところだったり。
Fanctor(S1:S)(S2:S)みたいな記法は今後色々使いそうです。