ファンクタはモジュールの一種なので、ファンクタにシグネチャを指定することができます。シグネチャの指定方法はモジュールと同じです。
(1) module ファンクタ名 (引数名: 型) : sig ... end = struct ... end (2) module ファンクタ名 (引数名: 型) = (struct ... end : sig ... end)
前回作成した二分木にシグネチャを付けると次のようになります。
リスト 1 : 二分木のシグネチャ
module MakeTree (Item: ItemType) :
sig
type tree
val create : tree
val search : Item.t -> tree -> Item.t option
val insert : Item.t -> tree -> tree
val search_min : tree -> Item.t
val search_max : tree -> Item.t
val delete_min : tree -> tree
val delete_max : tree -> tree
val delete : Item.t -> tree -> tree
val iter : (Item.t -> 'a) -> tree -> unit
end
= struct
... 省略 ...
end
データ型は type tree と宣言することでデータ構造の詳細を隠蔽します。ここで二分木の最大値を求める関数 search_max と最大値を削除する関数 delete_max を新たに追加しています。シグネチャをファンクタの中で指定しているので、シグネチャの中ではファンクタの引数 Item.t を参照することができます。
もちろん、シグネチャに名前を付けて、それをファンクタに指定することもできます。たとえば、次のようにシグネチャを定義したとしましょう。
リスト 2 ; シグネチャ TREE の定義 (エラー有り)
module type TREE =
sig
type tree
val create : tree
val search : Item.t -> tree -> Item.t option
val insert : Item.t -> tree -> tree
val search_min : tree -> Item.t
val search_max : tree -> Item.t
val delete_min : tree -> tree
val delete_max : tree -> tree
val delete : Item.t -> tree -> tree
val iter : (Item.t -> 'a) -> tree -> unit
end
ところが、このシグネチャは定義できません。Item.t が宣言されていないからです。そこで、シグネチャに型情報を追加するために with type 文を使います。with type の構文を示します。
with type 型名1 = 型式1 and type 型名2 = 型式2 and ... and type 型名n = 型式n
シグネチャでは "type 型名" だけを宣言しておいて、対応する型式を with type で指定します。たとえば、シグネチャ内の type t の型式は、with type t = int とすることで設定することができます。
with type を使ってシグネチャ TREE とファンクタ MakeTree を書き直すと次のようになります。
リスト 3 : 二分木のシグネチャ (2)
(* シグネチャ *)
module type TREE =
sig
type t
type tree
val create : tree
val search : t -> tree -> t option
val insert : t -> tree -> tree
val search_min : tree -> t
val search_max : tree -> t
val delete_min : tree -> tree
val delete_max : tree -> tree
val delete : t -> tree -> tree
val iter : (t -> 'a) -> tree -> unit
end
(* ファンクタ *)
module MakeTree (Item: ItemType) : (TREE with type t = Item.t) = struct
type t = Item.t
(* 節の定義 *)
type tree = Nil | Node of t * tree * tree
... 省略 ...
end
シグネチャで二分木に格納するデータ型を type t と宣言します。これを使ってシグネチャを記述します。シグネチャでデータ型 t を宣言しているので、ファンクタ (モジュール) でもシグネチャに合わせて type t を定義する必要があります。このとき、ファンクタ内では type t = Item.t とします。こうしないと、モジュールとシグネチャの型が合わずにエラーとなります。
あとは TREE の後ろで with type を使って type t の型式を Item.t に設定します。これでシグネチャとモジュールの型が一致してコンパイルすることができます。たとえば、整数を格納する IntTree を定義すると次のようになります。
# module IntTree = MakeTree(struct type t = int let compare x y = x - y end);;
module IntTree :
sig
type t = int
type tree
val create : tree
val search : t -> tree -> t option
val insert : t -> tree -> tree
val search_min : tree -> t
val search_max : tree -> t
val delete_min : tree -> tree
val delete_max : tree -> tree
val delete : t -> tree -> tree
val iter : (t -> 'a) -> tree -> unit
end
それでは実際に試してみましょう。
# open IntTree;; # let a0 = create;; val a0 : IntTree.tree = <abstr> # let a1 = insert 5 a0;; val a1 : IntTree.tree = <abstr> # let a2 = insert 3 a1;; val a2 : IntTree.tree = <abstr> # let a3 = insert 7 a2;; val a3 : IntTree.tree = <abstr> # search 3 a3;; - : int option = Some 3 # search 8 a3;; - : int option = None # iter (fun x -> print_int x; print_string " ") a3;; 3 5 7 - : unit = () # search_min a3;; - : IntTree.t = 3 # search_max a3;; - : IntTree.t = 7 # let a4 = delete_min a3;; val a4 : IntTree.tree = <abstr> # iter (fun x -> print_int x; print_string " ") a4;; 5 7 - : unit = () # let a5 = delete_max a4;; val a5 : IntTree.tree = <abstr> # iter (fun x -> print_int x; print_string " ") a5;; 5 - : unit = ()
OCaml のモジュールは高機能で、このほかにもモジュールを入れ子にしたり、ファンクタで複数の引数を受け取ることが可能です。これらの機能は本稿の範囲を超えるので、説明は割愛いたします。興味のある方は参考文献『プログラミング in OCaml』や OCaml のマニュアルをお読みください。
OCaml の標準ライブラリには、集合を表すモジュール Set と辞書 (連想配列) を表すモジュール Map が用意されています。どちらも変更不可 (immutable, 不変) なデータ構造で、実装には「平衡木」が用いられています。モジュールの生成にはファンクタ Make を使います。
module MapName = Map.Make(module) module SetName = Set.Make(moduel)
Make の引数 module はシグネチャ Map.OrderedType, Set.OrderedType を満たす必要があります。どちらも type t と val compare : t -> t -> int を定義すれば OK です。OCaml の標準ライブラリには、これらのシグネチャを満たすモジュール (Char, Int, Int32, Int64, Float, String など) が用意されているので、簡単に Set や Map を使用することができます。ただし、Int と Float は version 4.05.0 には無いので、使用することはできません。ご注意くださいませ。
簡単な使用例を示します。
$ rlwrap ocaml
OCaml version 4.10.0
# module IntMap = Map.Make(Int);;
module IntMap :
sig
type key = Int.t
type 'a t = 'a Map.Make(Int).t
val empty : 'a t
・・・省略・・・
val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
val of_seq : (key * 'a) Seq.t -> 'a t
end
# let m0 = List.fold_left (fun a (k, v) -> IntMap.add k v a) IntMap.empty [(1, 10); (2, 20); (3, 30)];;
val m0 : int IntMap.t = <abstr>
# IntMap.mem 1 m0;;
- : bool = true
# IntMap.mem 10 m0;;
- : bool = false
# IntMap.find_opt 1 m0;;
- : int option = Some 10
# IntMap.find_opt 10 m0;;
- : int option = None
# module IntSet = Set.Make(Int);;
module IntSet :
sig
type elt = Int.t
type t = Set.Make(Int).t
val empty : t
・・・省略・・・
val to_seq : t -> elt Seq.t
val add_seq : elt Seq.t -> t -> t
val of_seq : elt Seq.t -> t
end
# let s0 = List.fold_left (fun a x -> IntSet.add x a) IntSet.empty [5;6;4;7;3;8;2;9;1;0];;
val s0 : IntSet.t = <abstr>
# IntSet.mem 5 s0;;
- : bool = true
# IntSet.mem 50 s0;;
- : bool = false
# IntSet.find_opt 5 s0;;
- : IntSet.elt option = Some 5
# IntSet.find_opt 50 s0;;
- : IntSet.elt option = None
# IntSet.min_elt s0;;
- : IntSet.elt = 0
# IntSet.max_elt s0;;
- : IntSet.elt = 9
データの追加は関数 add で、データのチェックは関数 mem で、値の取得は関数 find や find_opt で、データの削除は関数 remove で行うことができます。詳しい説明は OCaml のマニュアルをお読みくださいませ。
(*
* tree.ml : 二分木
*
* Copyright (C) 2008-2020 Makoto Hiroi
*)
(* シグネチャ *)
module type ItemType = sig
type t
val compare : t -> t -> int
end
module type TREE =
sig
type t
type tree
val create : tree
val search : t -> tree -> t option
val insert : t -> tree -> tree
val search_min : tree -> t
val search_max : tree -> t
val delete_min : tree -> tree
val delete_max : tree -> tree
val delete : t -> tree -> tree
val iter : (t -> 'a) -> tree -> unit
end
(* ファンクタ *)
module MakeTree (Item: ItemType) : (TREE with type t = Item.t) = struct
type t = Item.t
(* 節の定義 *)
type tree = Nil | Node of t * tree * tree
(* 空の木 *)
let create = Nil
(* データの探索 *)
let rec search x = function
Nil -> None
| Node (y, _, _) when Item.compare x y = 0 -> Some y
| Node (y, left, _) when Item.compare x y < 0 -> search x left
| Node (_, _, right) -> search x right
(* データの挿入 *)
let rec insert x = function
Nil -> Node (x, Nil, Nil)
| (Node (y, _, _)) as node when Item.compare x y = 0 -> node
| Node (y, left, right) when Item.compare x y < 0 -> Node (y, (insert x left), right)
| Node (y, left, right) -> Node (y, left, (insert x right))
(* 最小値を求める *)
let rec search_min = function
Nil -> raise (Failure "search_min")
| Node (x, Nil, _) -> x
| Node (_, left, _) -> search_min left
(* 最小値を削除する *)
let rec delete_min = function
Nil -> raise (Failure "delete_min")
| Node (x, Nil, right) -> right
| Node (x, left, right) -> Node (x, (delete_min left), right)
(* 最大値を求める *)
let rec search_max = function
Nil -> raise (Failure "search_max")
| Node (x, _, Nil) -> x
| Node (_, _, right) -> search_max right
(* 最大値を削除する *)
let rec delete_max = function
Nil -> raise (Failure "delete_max")
| Node (x, left, Nil) -> left
| Node (x, left, right) -> Node (x, left, (delete_max right))
(* 削除 *)
let rec delete x = function
Nil -> raise Not_found
| Node(y, left, right) ->
if Item.compare x y = 0 then
if left = Nil then right
else if right = Nil then left
else
let min_data = search_min right in
Node (min_data, left, (delete_min right))
else if Item.compare x y < 0 then
Node (y, (delete x left), right)
else
Node (y, left, (delete x right))
(* 巡回 *)
let rec iter f = function
Nil -> ()
| Node (x, left, right) -> iter f left; f x; iter f right
end
type tree = Leaf | Node of tree * tree
バランスの取れたカッコ列と二分木は 1 対 1 に対応します。二分木を行きがけ順で巡回するとき、途中の節では左カッコ ( を出力して左右の枝をたどり、葉に到達したら右カッコ ) を出力すると、カッコ列を生成することができます。
リスト : 二分木をカッコ列に変換
(* 二分木の定義 *)
type tree = Leaf | Node of tree * tree
(* リストの最後尾の要素を削除する *)
let rec butlast = function
[] -> []
| [_] -> []
| x::xs -> x::(butlast xs)
let tree_to_kakko node =
let rec tree_sub = function
Leaf -> [")"]
| Node (left, right) -> "("::((tree_sub left) @ (tree_sub right))
in butlast (tree_sub node)
val butlast : 'a list -> 'a list = <fun> val tree_to_kakko : tree -> string list = <fun>
実際の処理は局所関数 tree_sub で行います。引数が Leaf の場合は右カッコを返します。引数が Node の場合は、tree_sub を再帰呼び出しして左部分木 left をたどり、それから右部分木 right をたどります。その結果を演算子 @ で連結して、先頭に左カッコを追加します。
ただし、最後に余分な右カッコが付いてくるので、関数 butlast で最後の要素を削除します。二分木の場合、葉 (Leaf) の個数を n とすると、節 (Node) の個数は n - 1 になります。カッコ列と違って L の個数が一つ多くなることに注意してください。
# tree_to_kakko (Node(Leaf, Leaf));;
- : string list = ["("; ")"]
# print_kakko (tree_to_kakko (Node(Leaf, Leaf)));;
()
- : unit = ()
# print_kakko (tree_to_kakko (Node(Node(Leaf, Leaf), Leaf)));;
(())
- : unit = ()
# print_kakko (tree_to_kakko (Node(Node(Leaf, Leaf), Node(Leaf, Leaf))));;
(())()
- : unit = ()
リスト : カッコ列を二分木に変換
(* カッコ列 (文字列) をリストに変換 *)
let rec string_to_list s =
let rec iter s n a =
if (String.length s) = n then List.rev a
else iter s (n + 1) ((Char.escaped s.[n])::a)
in iter s 0 []
let kakko_to_tree xs =
let rec kakko_sub = function
[] -> (Leaf, [])
| ")"::xs -> (Leaf, xs)
| "("::xs -> let (left, ys) = kakko_sub xs in
let (right, zs) = kakko_sub ys in
(Node(left, right), zs)
| _ -> raise (Failure "kakko_to_tree")
in fst (kakko_sub xs)
val string_to_list : string -> string list = <fun> val kakko_to_tree : string list -> tree = <fun>
実際の処理は局所関数 kakko_sub で行います。リストの先頭要素が右カッコの場合は (Leaf, xs) を返します。左カッコの場合は、kakko_sub を再帰呼び出しして左部分木 left を生成し、それから右部分木 right を生成します。あとは (Node(left, right), zs) を返すだけです。ただし、葉に対応する右カッコがひとつ少ないので、引数が空リストの場合は (Leaf, []) を返すようにします。
# kakko_to_tree (string_to_list "()()()");; - : tree = Node (Leaf, Node (Leaf, Node (Leaf, Leaf))) # kakko_to_tree (string_to_list "((()))");; - : tree = Node (Node (Node (Leaf, Leaf), Leaf), Leaf) # kakko_to_tree (string_to_list "()()()()");; - : tree = Node (Leaf, Node (Leaf, Node (Leaf, Node (Leaf, Leaf)))) # kakko_to_tree (string_to_list "(())(())");; - : tree = Node (Node (Leaf, Leaf), Node (Node (Leaf, Leaf), Leaf))