お気楽 OCaml プログラミング入門

ファンクタ (2)

●ファンクタのシグネチャ

ファンクタはモジュールの一種なので、ファンクタにシグネチャを指定することができます。シグネチャの指定方法はモジュールと同じです。

(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 を参照することができます。

●with type

もちろん、シグネチャに名前を付けて、それをファンクタに指定することもできます。たとえば、次のようにシグネチャを定義したとしましょう。

リスト 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 のモジュールは高機能で、このほかにもモジュールを入れ子にしたり、ファンクタで複数の引数を受け取ることが可能です。これらの機能は本稿の範囲を超えるので、説明は割愛いたします。興味のある方は参考文献 1 や OCaml のマニュアルをお読みください。

●Map と Set

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 には無いので、使用することはできません。ご注意くださいませ。

Int (version 4.10.0 以降)
Float (version 4.07.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

●問題

二分木 tree をカッコ列に変換する関数 tree_to_kakko tree

カッコ列は二分木に対応させることができる
tree の定義
```
type tree = Leaf | Node of tree * tree
```
Leaf が葉で、Node が節を表す

tree_to_kakko の逆変換を行う関数 kakko_to_tree kakko

●解答１

バランスの取れたカッコ列と二分木は 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))

初版 2008 年 7 月 13 日
改訂 2020 年 7 月 12 日

ハッシュ法

今回は高速な探索アルゴリズムの一つである「ハッシュ法」を取り上げます。OCaml には標準ライブラリにハッシュ法を実装したモジュール Hashtbl がありますが、今回は OCaml の勉強ということで、あえてハッシュ法のプログラムを作ってみることにします。なお、ハッシュ法は次のページで詳しく説明しています。よろしければ参考にしてください。

Algorithms with Python : ハッシュ法

ハッシュ法を理解されている方は読み飛ばしてもらってかまいません。

●ハッシュ法とは？

ハッシュ法は、コンパイラやインタプリタなどで予約語や関数名、変数名などの管理に使われている方法です。また、Perl, Python, Ruby など連想配列 (辞書) をサポートしているスクリプト言語がありますが、その実装にはハッシュ法が使われています。

ハッシュ法は「ハッシュ表 (hash table)」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function)」を使います。たとえば、ハッシュ表の大きさを N とすると、ハッシュ関数はデータを 0 から N - 1 までの整数値に変換します。この値を「ハッシュ値 (hash value)」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める方法がハッシュ法なのです。

ハッシュ法で不特定多数のデータを扱う場合、異なるデータでもハッシュ値が等しくなる可能性があります。これを「ハッシュ値の衝突 (collision)」といいます。つまり、データをハッシュ表に登録しようとしても、すでにデータが格納されていることがあるわけです。この場合、2 つの解決方法があります。

第 1 の方法は空いている場所を探して、そこにデータを格納する方法です。次の図を見てください。


        図 : ハッシュ法 (オープンアドレス法)

ハッシュ値が衝突した場合、異なるハッシュ関数を用いてハッシュ値を再計算し、データを格納する場所を決めます。これを空いている場所が見つかるまで繰り返します。この場合、データの最大数はハッシュ表の大きさに制限されます。

第 2 の方法はハッシュ表に複数のデータを格納することです。このとき、よく利用されるデータ構造が連結リストです。次の図を見てください。

ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。ただし、ハッシュ値の衝突が頻繁に発生すると連結リストが長くなるため、データの探索に時間がかかるようになります。したがって、効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。なお、連結リストの代わりに二分探索木を使う方法もあります。

これら 2 つの方法の名前ですが、参考文献によって呼び方が異なっていて統一されていません。このドキュメントでは参考文献 A に従って、第 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 としました。ハッシュ表の大きさは適当でもいいのですが、参考文献 B によると『この値が素数だと安心である』とのことなので、このプログラムでは 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 = ()

正常に動作していますね。

●ハッシュ法の長所と短所

ハッシュ法はデータを高速に検索できる優れたアルゴリズムです。データを検索するだけならば、二分探索木よりもハッシュ法が優れています。ですが、二分探索木にはハッシュ法にはない長所があります。二分探索木はデータの大小関係で構成されているので、左の木をたどることで最小値を、右の木をたどることで最大値を簡単に求めることができます。ハッシュ法で最大値や最小値を求めるには、すべてのデータを調べなければいけません。また、二分探索木では通りがけ順でデータを出力すれば、ソートされた結果を得ることができます。データの大小関係を処理する場合は、ハッシュ法よりも二分探索木を選ぶといいでしょう。

●Hashtbl の使い方

最後に、OCaml のモジュール Hashtbl (ハッシュ表) の基本的な使い方を簡単に説明します。ハッシュ表の生成には関数 create を使います。

Hashtbl.create init_size

引数 init_size はハッシュ表の初期サイズを指定します。これは適当な値でもかまいません。足りなくなったら自動的に拡張されます。

キーの有無は関数 mem でチェックすることができます。値の取得は関数 find や find_opt で、削除は関数 remove で行うことができます。簡単な使用例を示します。

# let h0 = Hashtbl.create 199;;
val h0 : ('_weak1, '_weak2) Hashtbl.t = <abstr>
# List.iter (fun (k, v) -> Hashtbl.add h0 k v) [("foo", 10); ("bar", 20); ("baz", 30)];;
- : unit = ()
# Hashtbl.mem h0 "foo";;
- : bool = true
# Hashtbl.mem h0 "foo1";;
- : bool = false
# Hashtbl.find_opt h0 "foo";;
- : int option = Some 10
# Hashtbl.find_opt h0 "foo1";;
- : int option = None
# Hashtbl.remove h0 "foo";;
- : unit = ()
# Hashtbl.mem h0 "foo";;
- : bool = false

詳しい説明は OCaml のマニュアル Module Hashtbl をお読みくださいませ。

●参考文献

近藤嘉雪, 『Ｃプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998
奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991

●プログラムリスト

(*
 * 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

初版 2008 年 7 月 13 日
改訂 2020 年 7 月 12 日

Functional Programming