ファンクタはモジュールの一種なので、ファンクタにシグネチャを指定することができます。シグネチャの指定方法はモジュールと同じです。
(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 delete : Item.t -> tree -> tree
val iter : (Item.t -> 'a) -> tree -> unit
end
= struct
... 省略 ...
end
データ型は type tree と宣言することでデータ構造の詳細を隠蔽します。関数 search_min と delete_min は非公開としました。今回はシグネチャをファンクタの中で指定しているので、シグネチャの中ではファンクタの引数 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 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 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 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 = ()
OCaml のモジュールは高機能で、このほかにもモジュールを入れ子にしたり、ファンクタで複数の引数を受け取ることが可能です。これらの機能は本稿の範囲を超えるので、説明は割愛いたします。興味のある方は 参考文献 [1] や OCaml のマニュアルをお読みください。
(*
* tree.ml : 二分木
*
* Copyright (C) 2008 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 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 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
今回は高速な探索アルゴリズムの一つである「ハッシュ法」を取り上げます。OCaml には標準ライブラリにハッシュ法を実装したモジュール HashTbl がありますが、今回は OCaml の勉強ということで、あえてハッシュ法のプログラムを作ってみることにします。なお、ハッシュ法は次のページで詳しく説明しています。内容は重複しますが、ご了承くださいませ。
ハッシュ法を理解されている方は読み飛ばしてもらってかまいません。
ハッシュ法は、コンパイラやインタプリタなどで予約語や関数名、変数名などの管理に使われている方法です。また、Perl, Python, Ruby など連想配列 (辞書) をサポートしているスクリプト言語がありますが、その実装にはハッシュ法が使われています。
ハッシュ法は「ハッシュ表 (hash table) 」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function) 」を使います。たとえば、ハッシュ表の大きさを N とすると、ハッシュ関数はデータを 0 から N - 1 までの整数値に変換します。この値を「ハッシュ値 (hash value) 」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める方法がハッシュ法なのです。
ハッシュ法で不特定多数のデータを扱う場合、異なるデータでもハッシュ値が等しくなる可能性があります。これを「ハッシュ値の衝突 (collision) 」といいます。つまり、データをハッシュ表に登録しようとしても、すでにデータが格納されていることがあるわけです。この場合、2 つの解決方法があります。
第 1 の方法は空いている場所を探して、そこにデータを格納する方法です。次の図を見てください。
ハッシュ表 ハッシュ表
┌───┐ ┌───┐
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ａ │ │ Ａ ┼─┐ 衝突 (E)
├───┤ ├───┤ │
│ ／ │ │ Ｅ │←┘
├───┤ ├───┤
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ｂ │ │ Ｂ ┼─┐ 衝突 (D, F)
├───┤ ├───┤ │
│ ／ │ │ Ｄ ┼←┤ 衝突 (F)
├───┤ ├───┤ │
│ Ｃ │ │ Ｃ ┼←┤ 衝突 (F)
├───┤ ├───┤ │
│ ／ │ │ Ｆ │←┘
└───┘ └───┘
／ ： 空き場所
(1) A, B, C を登録 (2) D, E, F を登録
図 1 : ハッシュ法 (オープンアドレス法)
ハッシュ値が衝突した場合、異なるハッシュ関数を用いてハッシュ値を再計算し、データを格納する場所を決めます。これを空いている場所が見つかるまで繰り返します。この場合、データの最大数はハッシュ表の大きさに制限されます。
第 2 の方法はハッシュ表に複数のデータを格納することです。このとき、よく利用されるデータ構造が連結リストです。次の図を見てください。
ハッシュ表
┌───┐
│ ／ │
├───┤ ┌─┬─┐ ┌─┬─┐
│ ・─┼─→│Ｅ│・┼→│Ａ│／│
├───┤ └─┴─┘ └─┴─┘
│ ／ │
├───┤
│ ／ │
├───┤ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ ・─┼─→│Ｆ│・┼→│Ｄ│・┼→│Ｂ│／│
├───┤ └─┴─┘ └─┴─┘ └─┴─┘
│ ／ │
├───┤ ┌─┬─┐
│ ・─┼─→│Ｃ│／│
├───┤ └─┴─┘
│ ／ │
└───┘
／ ： 終端
図 2 : ハッシュ法 (チェイン法)
ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。ただし、ハッシュ値の衝突が頻繁に発生すると連結リストが長くなるため、データの探索に時間がかかるようになります。したがって、効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。なお、連結リストの代わりに二分探索木を使う方法もあります。
これら 2 つの方法の名前ですが、参考文献によって呼び方が異なっていて統一されていません。このドキュメントでは 参考文献 1 に従って、第 1 の方法を「オープンアドレス法 (open addressing) 」、第 2 の方法を「チェイン法 (chaining) 」と呼ぶことにします。
今回はチェイン法でプログラムを作ってみましょう。ハッシュ表にはキーとそれに対応する値を格納することにします。ハッシュ法の性能は、ハッシュ関数によって大きく左右されます。このため、データに適したハッシュ関数を作るのが普通です。そこで、ハッシュ表の大きさ、ハッシュ関数、データの比較関数はストラクチャにまとめておき、ファンクタに渡すことにします。
最初に、ファンクタに渡すストラクチャ用のシグネチャ ITEMTYPE を定義します。次のリストを見てください。
リスト 4 : シグネチャの定義
module type ITEMTYPE =
sig
type t
val hash_size : int
val hash_func : t -> int
val equal : t -> t -> bool
end
type t がキーとなるデータ型、hash_size がハッシュ表の大きさ、hash_func がハッシュ関数、equal がデータが等しいかチェックする述語です。これらの変数と関数を使ってファンクタを定義します。次のリストを見てください。
リスト 5 : ファンクタの定義
module MakeHash (Item: ITEMTYPE) :
sig
type t = Item.t
type 'a hash
val create : unit -> 'a hash
val insert : t -> 'a -> 'a hash -> unit
val search : t -> 'a hash -> 'a option
val delete : t -> 'a hash -> unit
val iter : (t -> 'a -> unit) -> 'a hash -> unit
end
= struct
(* 型の定義 *)
type t = Item.t
type 'a pair = {key : t; mutable value : 'a}
type 'a hash = Hash of 'a pair list array
(* リストから pair を探す *)
let rec find k = function
[] -> None
| ({key = x; value = _} as p) :: _ when Item.equal k x -> Some p
| _ :: xs -> find k xs
(* ハッシュ表の位置を求める *)
let position key = (Item.hash_func key) mod Item.hash_size
(* 生成 *)
let create () = Hash (Array.make Item.hash_size [])
(* 挿入 *)
let insert k v (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> table.(n) <- {key = k; value = v} :: table.(n)
| Some p -> p.value <- v
(* 探索 *)
let search k (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> None
| Some p -> Some p.value
(* 削除 *)
let delete k (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> raise Not_found
| Some p -> table.(n) <- List.filter (fun x -> x <> p) table.(n)
(* 巡回 *)
let iter f (Hash (table)) =
for n = 0 to Item.hash_size - 1 do
List.iter (fun {key = k; value = v} -> f k v) table.(n)
done
end
最初に type でキーとなるデータ型 t を Item.t と宣言します。値は型変数 'a で表します。キーと値はレコード {key : t; mutable value : 'a} に格納し、それをデータ型 'a pair とします。すると、ハッシュ表のデータ型は 'a hash = Hash of 'a pair list array と定義することができます。
関数 find はキー k と等しい pair をリストから探します。キーの比較は Item.eaual を使います。見つけたレコードは option に格納して返します。関数 position はキー key からハッシュ表の位置を計算します。Item.hash_func で key のハッシュ値を求め、それと Item.hash_size の剰余を計算するだけです。この 2 つの関数は非公開とします。
関数 create はハッシュ表を生成します。Array.make で大きさ Item.hash_size の配列を生成するだけです。初期値は空リストになります。
データの挿入は関数 insert で行います。引数 k がキー、v が値、table がハッシュ表です。position でハッシュ表の位置 (添字) を求めます。そして、find で k と等しい pair を探します。見つからない場合はリストの先頭にレコードを追加します。見つかった場合は、レコードのフィールド value の値を v に書き換えます。
データの探索は関数 search で行います。find で k と等しい pair を探して、見つからない場合は None を返し、見つけた場合はフィールド value の値を option に格納して返します。
データの削除は関数 delete で行います。find で k と等しい pair を探します。見つからない場合は例外 Not_found を送出します。見つけた場合はその pair を削除します。この処理は List.filter を使うと簡単です。
関数 iter はハッシュ表に格納された全要素に対して関数 f を適用します。for ループでハッシュ表の要素 (リスト) を取り出し、List.iter でリストに格納されているレコードを取り出します。あとは関数 f にキー k と値 v を渡して呼び出すだけです。
次はファンクタに渡すストラクチャを定義しましょう。格納するデータは文字列とします。次のリストを見てください。
リスト 6 : ストラクチャの定義
module StringItem = struct
type t = string
let hash_size = 199
let hash_func key =
let rec string_hash n a =
if String.length key = n then a
else string_hash (n + 1) (a + int_of_char key.[n])
in
string_hash 0 0
let equal x y = x = y
end
module StringHash = MakeHash(StringItem)
ストラクチャ名は StringItem としました。ハッシュ表の大きさは適当でもいいのですが、参考文献 2 によると 『この値が素数だと安心である』 とのことなので、このプログラムでは 199 としました。
今回はハッシュ法の例題ということで、ハッシュ値の計算は簡単な方法を採用します。関数 hash_func は文字コードをすべて加算した値を返します。その値を hash_size で割った余りがハッシュ値になりま。これで、0 から 198 までのハッシュ値を生成することができます。
関数 equal は等値演算子 = でデータを比較するだけです。これで、ストラクチャの定義は終わりです。最後に、ファンクタ MakeHash に StringItem を渡してストラクチャ StringHash を生成します。実際に StringHash を生成すると次のように表示されます。
module StringHash :
sig
type t = StringItem.t
type 'a hash = 'a MakeHash(StringItem).hash
val create : unit -> 'a hash
val insert : t -> 'a -> 'a hash -> unit
val search : t -> 'a hash -> 'a option
val delete : t -> 'a hash -> unit
val iter : (t -> 'a -> unit) -> 'a hash -> unit
end
それでは簡単な実行例を示します。
# open StringHash;; # let a = create ();; val a : 'a StringHash.hash = <abstr> # insert "abc" 10 a;; - : unit = () # insert "def" 20 a;; - : unit = () # insert "ghi" 30 a;; - : unit = () # search "abc" a;; - : int option = Some 10 # search "ab" a;; - : int option = None # delete "abc" a;; - : unit = () # search "abc" a;; - : int option = None # iter (fun k v -> print_string (k ^ " "); print_int v; print_newline ()) a;; def 20 ghi 30 - : unit = ()
正常に動作していますね。
ハッシュ法はデータを高速に検索できる優れたアルゴリズムです。データを検索するだけならば、二分探索木よりもハッシュ法が優れています。ですが、二分探索木にはハッシュ法にはない長所があります。二分探索木はデータの大小関係で構成されているので、左の木をたどることで最小値を、右の木をたどることで最大値を簡単に求めることができます。ハッシュ法で最大値や最小値を求めるには、すべてのデータを調べなければいけません。また、二分探索木では通りがけ順でデータを出力すれば、ソートされた結果を得ることができます。データの大小関係を処理する場合は、ハッシュ法よりも二分探索木を選ぶといいでしょう。
(*
* hash.ml : ハッシュ法
*
* Copyright (C) 2008 Makoto Hiroi
*)
(* シグネチャ *)
module type ITEMTYPE =
sig
type t
val hash_size : int
val hash_func : t -> int
val equal : t -> t -> bool
end
(* ファンクタ *)
module MakeHash (Item: ITEMTYPE) :
sig
type t = Item.t
type 'a hash
val create : unit -> 'a hash
val insert : t -> 'a -> 'a hash -> unit
val search : t -> 'a hash -> 'a option
val delete : t -> 'a hash -> unit
val iter : (t -> 'a -> unit) -> 'a hash -> unit
end
= struct
(* 型の定義 *)
type t = Item.t
type 'a pair = {key : t; mutable value : 'a}
type 'a hash = Hash of 'a pair list array
(* リストから pair を探す *)
let rec find k = function
[] -> None
| ({key = x; value = _} as p) :: _ when Item.equal k x -> Some p
| _ :: xs -> find k xs
(* ハッシュ表の位置を求める *)
let position key = (Item.hash_func key) mod Item.hash_size
(* 生成 *)
let create () = Hash (Array.make Item.hash_size [])
(* 挿入 *)
let insert k v (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> table.(n) <- {key = k; value = v} :: table.(n)
| Some p -> p.value <- v
(* 探索 *)
let search k (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> None
| Some p -> Some p.value
(* 削除 *)
let delete k (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> raise Not_found
| Some p -> table.(n) <- List.filter (fun x -> x <> p) table.(n)
(* 巡回 *)
let iter f (Hash (table)) =
for n = 0 to Item.hash_size - 1 do
List.iter (fun {key = k; value = v} -> f k v) table.(n)
done
end