ハッシュ法
今回は高速な探索アルゴリズムの一つである「ハッシュ法」を取り上げます。最初にハッシュ法を簡単に説明します。ハッシュ法を理解されている方は読み飛ばしてもらってかまいません。
次へ
●ハッシュ法とは？
ハッシュ法は、コンパイラやインタプリタなどで予約語や関数名、変数名などの管理に使われている方法です。また、Perl、Python, Ruby など連想配列をサポートしているスクリプト言語がありますが、その実装にはハッシュ法が使われています。
ハッシュ法は「ハッシュ表 (hash table)」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function)」を使います。たとえば、ハッシュ表の大きさを N とすると、ハッシュ関数はデータを 0 から N - 1 までの整数値に変換します。この値を「ハッシュ値 (hash value)」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める方法がハッシュ法なのです。
ハッシュ法で不特定多数のデータを扱う場合、異なるデータでもハッシュ値が等しくなる可能性があります。これを「ハッシュ値の衝突 (collision)」といいます。つまり、データをハッシュ表に登録しようとしても、すでにデータが格納されていることがあるわけです。この場合、2 つの解決方法があります。
第 1 の方法は空いている場所を探して、そこにデータを格納する方法です。次の図を見てください。
図 : ハッシュ法 (オープンアドレス法)
ハッシュ値が衝突した場合、異なるハッシュ関数を用いてハッシュ値を再計算し、データを格納する場所を決めます。これを空いている場所が見つかるまで繰り返します。この場合、データの最大数はハッシュ表の大きさに制限されます。
第 2 の方法はハッシュ表に複数のデータを格納することです。このとき、よく利用されるデータ構造が連結リストです。次の図を見てください。
ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。ただし、ハッシュ値の衝突が頻繁に発生すると連結リストが長くなるため、データの探索に時間がかかってしまいます。効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。連結リストの代わりに二分探索木を使う方法もあります。
これら 2 つの方法の名前ですが、参考文献によって呼び方が異なっていて統一されていません。このドキュメントでは 参考文献 [1] に従って、第 1 の方法を「オープンアドレス法 (open addressing)」、第 2 の方法を「チェイン法 (chaining)」と呼ぶことにします。
●プログラムの作成
今回はチェイン法でプログラムを作ってみましょう。ハッシュ法の性能は、ハッシュ関数によって大きく左右されます。このため、データに適したハッシュ関数を作るのが普通です。そこで、ハッシュ表の大きさ、ハッシュ関数、データの比較関数はストラクチャにまとめておき、ファンクタに渡すことにします。
最初に、ファンクタに渡すストラクチャ用のシグネチャ HASHITEM を定義します。次のリストを見てください。
リスト : シグネチャの定義
signature HASHITEM = sig
type item
val size : int
val hash_func : item -> int
val equal : item * item -> bool
end
size がハッシュ表の大きさ、hash_func がハッシュ関数、equal がデータが等しいかチェックする述語です。これらの変数と関数を使ってファンクタを定義します。次のリストを見てください。
リスト : ファンクタの定義
functor makeHash(Item: HASHITEM) = struct
(* データ型の定義 *)
datatype 'a hash = Hash of 'a list array
(* ハッシュ表の生成 *)
fun create () = Hash(Array.array(Item.size, nil: Item.item list))
(* データの探索 *)
fun search(k, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
List.find (fn x => Item.equal(x, k)) xs
end
fun member(k, ht) = isSome (search(k, ht))
(* データの挿入 *)
fun insert(k, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
if List.exists (fn x => Item.equal(x, k)) xs then ()
else Array.update(table, n, k::xs)
end
(* データの削除 *)
fun delete(k, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
Array.update(table, n, List.filter (fn x => not(Item.equal(x, k))) xs)
end
end
最初に datatype でハッシュ表のデータ型 'a hash を定義します。配列をそのまま使うのではなく、ハッシュ表を表すデータ型を定義した方がよいでしょう。関数 create でハッシュ表を生成します。大きさ は Item.size で、初期値は空リスト (nil) になります。
データの探索は関数 search で行います。ハッシュ関数 hash_func でハッシュ値 n を求め、ハッシュ表 table からリスト xs を取り出します。そして、関数 find で k と等しいデータを探します。データの比較には関数 equal を使います。関数 find は option 型を返しますが、関数 member はデータの有無を bool (true, false) で返します。
データの挿入は関数 insert で行います。ハッシュ値 n をリスト xs を求める処理は search と同じです。まず、関数 exists で同じデータがあるかチェックします。もし、同じデータがあれば何もせずにユニットを返します。そうでなければ、k をリスト xs の先頭に追加します。そして、ハッシュ表 table を関数 update で更新します。
データの削除は関数 delete で行います。ハッシュ値 n をリスト xs を求める処理は insert と同じです。あとは List.filter を使って data と等しい要素を削除し、その結果をハッシュ表 table にセットするだけです。
●ハッシュ関数の作成
次はファンクタに渡すストラクチャを定義しましょう。格納するデータは文字列とします。次のリストを見てください。
リスト : ストラクチャの定義
structure StringItem: HASHITEM = struct
type item = string
val size = 199
fun hash_func x = (foldr (fn(a, b) => ord(a) + b) 0 (explode x)) mod size
fun equal(a, b) = a = b
end
structure StringHash = makeHash(StringItem)
ストラクチャ名は StringItem としました。ハッシュ表の大きさは適当でもいいのですが、参考文献 [2] によると 『この値が素数だと安心である』 とのことなので、このプログラムでは 199 としました。
今回はハッシュ法の例題ということで、ハッシュ値の計算は簡単な方法を採用します。関数 hash_func は文字コードを全て加算し、その値を size で割った余りをハッシュ値としています。これで、0 から 198 までのハッシュ値を生成することができます。
SML/NJ には、文字を表す「文字型 (char)」というデータ型があります。c を文字とすると、文字型は #"c" で表します。SML/NJ には string を char list に変換する関数 explode と、char list を string に変換する関数 implode が用意されています。簡単な例を示します。
- explode "foo";
val it = [#"f",#"o",#"o"] : char list
- implode it;
val it = "foo" : string
char を int に変換する関数が ord で、int を char に変換する関数が chr です。簡単な例を示します。
- ord #"a";
val it = 97 : int
- chr 97;
val it = #"a" : char
関数 hash_func は引数の文字列 x を explode で分解し、foldr で文字コードを加算します。匿名関数の中では、ord を使って char を int に変換し、その値を引数 b に加算します。あとは、foldr の返り値と size の剰余を求めるだけです。
文字列は等値型データなので、関数 equal は等値演算子 = でデータを比較するだけです。これで、ストラクチャの定義は終わりです。最後に、ファンクタ makeHash に StringItem を渡してストラクチャ StringHash を生成します。
●実行例
それでは簡単な実行例を示します。
- val a = StringHash.create();
val a = Hash [|[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],...|]
: StringItem.item StringHash.hash
- StringHash.insert("foo", a);
val it = () : unit
- StringHash.search("foo", a);
val it = SOME "foo" : StringItem.item option
- StringHash.member("foo", a);
val it = true : bool
- StringHash.search("bar", a);
val it = NONE : StringItem.item option
- StringHash.member("bar", a);
val it = false : bool
- StringHash.delete("foo", a);
val it = () : unit
- StringHash.search("foo", a);
val it = NONE : StringItem.item option
正常に動作していますね。
●連想配列 (Hash Table) の実装
最後にハッシュ法を使って「連想配列」を作ってみましょう。なお、SML/NJ の The Util Library には連想配列として利用できるストラクチャ HashTable が用意されているので、私たちが自作する必要はありませんが、SML/NJ のお勉強ということで、プログラムを作ることにします。
チェイン法の場合、連想リストを使うと簡単です。データ型の定義は次のようになります。
リスト : 連想配列
functor makeHashtbl(Item: HASHITEM) = struct
(* データ型の定義 *)
datatype ('a, 'b) hash = Hash of ('a * 'b) list array
(* ハッシュ表の生成 *)
fun create () = Hash(Array.array(Item.size, nil: ('a * 'b) list))
・・・省略・・・
end
(* キーが文字列の連想配列 *)
structure StringHashtbl = makeHashtbl(StringItem)
ファンクタ名は makeHashtbl としました。HASHITEM の型 item をキーとして使います。データ型は ('a, 'b) hash で、型変数 'a がキーのデータ型、'b が値のデータ型を表します。なお、値のデータ型が定義されていないので、関数 create でハッシュ表を生成するとき、多相性の制約によりデータ型の指定が必要になります。たとえば、キーが文字列で値が整数の場合は次のように指定します。
- val a : (string, int) StringHashtbl.hash = StringHashtbl.create();
val a = Hash [|[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],...|]
: (string,int) StringHashtbl.hash
関数 search はキーが見つかれば SOME 値 を返し、見つからなければ NONE を返します。member もキーが見つかれば true を、そうでなければ false を返します。関数 insert は連想リストの先頭に組 (キー, 値) を追加するだけです。関数 delete は List.filter で同じキーを持つ組を削除します。とくに難しいところはないので、詳細は プログラムリスト をお読みくださいませ。
●実行例 (2)
簡単な実行例を示します。
- val a : (string, int) StringHashtbl.hash = StringHashtbl.create();
val a = Hash [|[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],...|]
: (string,int) StringHashtbl.hash
- StringHashtbl.insert("foo", 100, a);
val it = () : unit
- StringHashtbl.search("foo", a);
val it = SOME 100 : int option
- StringHashtbl.search("bar", a);
val it = NONE : int option
- StringHashtbl.insert("foo", 200, a);
val it = () : unit
- StringHashtbl.search("foo", a);
val it = SOME 200 : int option
- StringHashtbl.delete("foo", a);
val it = () : unit
- StringHashtbl.search("foo", a);
val it = NONE : int option
正常に動作しているようです。興味のある方はいろいろ試してみてください。
●プログラムリスト
(*
* hash.sml : ハッシュ法
*
* Copyright 2005-2020 Makoto Hiroi
*
*)
(* シグネチャ *)
signature HASHITEM = sig
type item
val size : int
val hash_func : item -> int
val equal : item * item -> bool
end
(* ファンクタ *)
functor makeHash(Item: HASHITEM) = struct
(* データ型の定義 *)
datatype 'a hash = Hash of 'a list array
(* ハッシュ表の生成 *)
fun create () = Hash(Array.array(Item.size, nil: Item.item list))
(* データの探索 *)
fun search(k, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
List.find (fn x => Item.equal(x, k)) xs
end
fun member(k, ht) = isSome (search(k, ht))
(* データの挿入 *)
fun insert(k, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
if List.exists (fn x => Item.equal(x, k)) xs then ()
else Array.update(table, n, k::xs)
end
(* データの削除 *)
fun delete(k, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
Array.update(table, n, List.filter (fn x => not(Item.equal(x, k))) xs)
end
end
structure StringItem: HASHITEM = struct
type item = string
val size = 199
fun hash_func x = (foldr (fn(a, b) => ord(a) + b) 0 (explode x)) mod size
fun equal(a, b) = a = b
end
structure StringHash = makeHash(StringItem)
(* 連想配列 *)
functor makeHashtbl(Item: HASHITEM) = struct
(* データ型の定義 *)
datatype ('a, 'b) hash = Hash of ('a * 'b) list array
(* ハッシュ表の生成 *)
fun create () = Hash(Array.array(Item.size, nil: ('a * 'b) list))
(* データの探索 *)
fun search(k, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
case List.find (fn(x, _) => Item.equal(x, k)) xs
of NONE => NONE
| SOME (_, v) => SOME v
end
fun member(k, ht) = isSome (search(k, ht))
(* データの挿入 *)
fun insert(k, v, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
Array.update(table, n, (k, v)::xs)
end
(* データの削除 *)
fun delete(k, Hash table) =
let
val n = Item.hash_func k
val xs = Array.sub(table, n)
in
Array.update(table, n, List.filter (fn(x, _) => not(Item.equal(x, k))) xs)
end
end
structure StringHashtbl = makeHashtbl(StringItem)
初版 2005 年 6 月 4 日
改訂 2020 年 8 月 16 日
モジュール (3)
前回までで、ストラクチャ、シグネチャ、ファンクタというモジュールの基本的な機能を一通り説明しました。このほかにも、SML/NJ のモジュールには便利な機能がいくつかあります。今回は「キュー (queue)」というデータ構造を例題にして、いろいろなモジュール機能を紹介します。
●キューとは？
キューは「待ち行列」といわれるデータ構造です。たとえばチケットを買う場合、窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。
キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。
ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。たとえば、データの追加に演算子 @ を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると時間がかかるようになります。
これを回避する方法はいろいろ考えられるのですが、今回は SML/NJ でよく使われている方法を紹介します。次の図を見てください。
上図は 2 つのリストでキューを表しています。データを取り出すときは front のリストを、データを追加するときは rear のリストを使います。front と rear で一つのキューを構成し、rear のリストはデータを逆順で格納することになります。ようするに、front が先頭で rear が最後尾になるわけです。上図のキューを一つのリストで表すと [0, 1, 2, 3, 4, 5] になります。
したがって、front が空リストでも rear にデータがあれば、キューは空ではありません。rear のリストを逆順にして front にセットし、rear を空リストにします。これで front からデータを取り出すことができます。キューが空の状態は front と rear が両方とも空リストの場合です。
●キューの実装
それではプログラムを作りましょう。次のリストを見てください。
リスト : キューの実装
structure Queue = struct
datatype 'a queue = Q of 'a list * 'a list
exception EmptyQueue
val create = Q(nil, nil)
fun enqueue(Q(front, rear), x) = Q(front, x::rear)
fun dequeue(Q(nil, nil)) = raise EmptyQueue
| dequeue(Q(nil, rear)) = dequeue(Q(rev rear, nil))
| dequeue(Q(x::xs, rear)) = Q(xs, rear)
fun front(Q(nil, nil)) = raise EmptyQueue
| front(Q(nil, rear)) = front(Q(rev rear, nil))
| front(Q(x::xs, _)) = x
fun isEmpty(Q(nil, nil)) = true
| isEmpty _ = false
end
まず datatype でデータ型 'a queue を定義します。型式は 'a list * 'a list で、組の第 1 要素が front で第 2 要素が rear になります。例外 EmptyQueue は、空のキューからデータを取り出そうとしたときに送出します。キューの生成には変数 create を使います。create の値は空のキュー Q(nil, nil) です。
関数 equeue はキューにデータ x を追加します。これは x を rear の先頭に追加するだけです。関数 dequeue はキューからデータを取り除きます。キューが空の場合は例外 EmptyQueue を送出します。front が空リストの場合は、キュー Q(rev rear, nil) を作って dequeue を再帰呼び出しします。front にデータがある場合は先頭要素を取り除くだけです。関数 front はキューの先頭要素を返します。処理は dequeue とほとんど同じで、違いは front の先頭データ x を返すだけです。関数 isEmpty は、キューが空であれば true を、そうでなければ false を返します。
それでは簡単な実行例を示します。
- val a = Queue.create;
val a = Q ([],[]) : 'a Queue.queue
- val b = Queue.enqueue(a, 1);
val b = Q ([],[1]) : int Queue.queue
- val c = Queue.enqueue(b, 2);
val c = Q ([],[2,1]) : int Queue.queue
- val d = Queue.dequeue c;
val d = Q ([2],[]) : int Queue.queue
- Queue.front d;
val it = 2 : int
きちんと動作していますね。
●データ抽象
ストラクチャで定義された変数や関数は、シグネチャを定義することで外部から隠すことができます。datatype で定義されたデータ構成子も、シグネチャに datatype を記述しなければ利用することはできません。たとえば、次のようにシグネチャを定義して IntQueue を作ります。
リスト : シグネチャの定義
signature INTQUEUE = sig
type 'a queue
val create : int queue
val dequeue : int queue -> int queue
val enqueue : int queue * int -> int queue
val front : int queue -> int
val isEmpty : int queue -> bool
end
structure IntQueue: INTQUEUE = Queue
ストラクチャ Queue は datatype が公開されるので、データ構成子 Q を利用することができます。IntQueue はシグネチャ INTQUEUE に datatype を記述していないので、データ構成子 Q を使うことはできません。簡単な例を示します。
- val a = Queue.Q(nil, nil);
val a = Q ([],[]) : 'a Queue.queue
- val b = IntQueue.Q(nil, nil);
stdIn:14.9-14.19 Error: unbound variable or constructor: Q in path IntQueue.Q
- val c = IntQueue.create;
val c = Q ([],[]) : int Queue.queue
このように、IntQueue のデータ構成子 Q は使うことができません。しかしながら、キューのデータ構造が表示されるところは変わりありません。データ構造も隠しておきたい場合は abstype を使います。
abstype データ型定義 with
...
end
abstype は「抽象型 (abstract type)」といい、データ構成子を隠すことができます。データ型の定義は datatype とほとんど同じで、その後ろに with を続けます。そして、with と end の間に、データ構成子を使う関数、変数、例外などを記述します。abstype はストラクチャの中でも定義することができます。abstype を使って Queue を書き直すと次のようになります。
リスト : 抽象型データの定義
structure Queue = struct
abstype 'a queue = Q of 'a list * 'a list with
exception EmptyQueue
val create = Q(nil, nil)
fun enqueue(Q(front, rear), x) = Q(front, x::rear)
fun dequeue(Q(nil, nil)) = raise EmptyQueue
| dequeue(Q(nil, rear)) = dequeue( Q(rev rear, nil) )
| dequeue(Q(x::xs, rear)) = Q(xs, rear)
fun front(Q(nil, nil)) = raise EmptyQueue
| front(Q(nil, rear)) = front(Q(rev rear, nil))
| front(Q(x::xs, _)) = x
fun isEmpty(Q(nil, nil)) = true
| isEmpty _ = false
end
end
datatype を abstype に変更し、with と end の間に変数、関数、例外を定義しただけです。とても簡単ですね。実行例は次のようになります。
- val a = Queue.create;
val a = - : 'a Queue.queue
- val b = Queue.enqueue(a, 10);
val b = - : int Queue.queue
- Queue.front b;
val it = 10 : int
ストラクチャ Queue を定義すると、そのシグネチャにはデータ構造の定義が記述されていません。また、Queue のデータ構造も表示されません。
このように、データ構造の詳細を隠蔽し、操作関数を使ってデータ構造にアクセスすることを「データ抽象 (data abstraction)」とか「カプセル化 (encapsulation)」といいます。わざわざ操作関数を用意するのは面倒なように思われますが、そのことによりプログラムも読みやすくなり、修正にも強いプログラムを作ることができます。
たとえば、キューの実装をリストから配列に変更することを考えてみましょう。この場合、datatype の定義はリストから配列に変更されます。もしも、データ構成子 Q を使って直接キューを操作しているプログラムがあるならば、その箇所を探して修正する必要があります。操作関数だけを使っていて、操作関数の仕様が変わらなければ、キューを使うプログラムを修正する必要はありません。ストラクチャ Queue を変更するだけで済むわけです。
●local と open
関数や変数を非公開にする方法は、ストラクチャとシグネチャのほかに local 宣言があります。
local ... in ... end
local と in の間に定義された関数や変数は非公開になり、in と end の間に定義された関数や変数が公開されます。次のリストを見てください。
リスト : local による局所定義
local
fun facti( 0, a ) = a
| facti( n, a ) = facti( n - 1, n * a )
in
fun fact( n ) = facti( n, 1 )
end
local と in の間に定義されている関数 facti は外部に公開されません。facti を呼び出すことができるのは、in と end の間に定義されている関数 fact だけです。実際に実行すると、次のようになります。
val fact = fn : int -> int
- fact(10);
val it = 3628800 : int
local は式ではないので、値を返しません。この例では関数 facti と fact が定義されますが、外部に公開されるのは fact だけです。local はストラクチャの内部や abstype の with ... end の内部などで用いることができます。
ところで、ストラクチャ内で定義されている変数や関数は、ストラクチャ名とドット ( . ) を付加して参照することができます。IntQueue 内の関数であれば、IntQueue.create や IntQueue.enqueue のようになります。ストラクチャ名をつけるのが面倒な場合は open 宣言を使います。
open ストラクチャ名
open はストラクチャをオープンして、ストラクチャ名をつけなくてもストラクチャ内の関数や変数を参照することができます。次の例を見てください。
- open IntQueue;
opening IntQueue
datatype 'a queue = ...
val create : int queue
val dequeue : int queue -> int queue
val enqueue : int queue * int -> int queue
val front : int queue -> int
val isEmpty : int queue -> bool
- val a = create;
val a = Q ([],[]) : int queue
- val b = enqueue( a, 1 );
val b = Q ([],[1]) : int queue
このように、open を使うと IntQueue をつけなくても変数や関数を参照することができます。ただし、注意事項があります。open はストラクチャ内で定義されている「変数束縛」を、現在の「環境」に追加しているだけです。つまり、次の動作と同じです。
val create = IntQueue.create;
val dequeue = IntQueue.dequeue;
val enqueue = IntQueue.enqueue;
val front = IntQueue.front;
val isEmpty = IntQueue.isEmpty;
対話モードで open を実行すると、ストラクチャ内の変数束縛は対話モードの環境に追加されます。対話モードの環境を「トップレベルの環境」といいます。トップレベルの環境には、あらかじめ定義されている関数や変数があります。open でストラクチャ内の変数や関数を環境に追加するとき、同じ名前が存在している場合はどうなるのでしょうか。次の例を見てください。
- val a = 10;
val a = 10 : int
- a;
val it = 10 : int
- val a = "foo";
val a = "foo" : string
- a;
val it = "foo" : string
val による変数の定義は、変数束縛を生成して環境に追加するだけです。変数束縛を変数名と値の組で、環境を連想リストで表すとわかりやすいと思います。最初、環境は空リスト (nil) とします。次の図を見てください。
環境
---------------------------------------
[ ]
val a = 10 ==> [(a, 10)]
val a = "foo" ==> [(a, "foo"), (a, 10)]
val a = 10 は変数束縛 (a, 10) を生成して環境に追加します。環境は [ (a, 10) ] になります。環境から値を求める場合は、連想リストの探索と同じです。連想リストの先頭から変数 a を探し、最初に見つけた変数束縛の値を返します。この場合、変数 a の値は 10 になります。
次の val a = "foo" も同様に、(a, "foo") を生成して環境に追加します。このとき、連想リストの先頭に追加するので、環境は [ (a, "foo"), (a, 10) ] になります。変数 a の値を求めると、最初に見つかる変数束縛は (a, "foo") なので、変数 a の値は "foo" になります。
結果だけを見ると、変数 a の値を書き換えているように見えますが、実際は新しい変数束縛を生成して環境に追加しているだけなのです。環境には前の変数束縛も残っています。しかしながら、追加した変数束縛によって隠されてしまうので、前の変数束縛にアクセスすることはできません。
open を使う場合、環境に同じ名前があると、その名前を隠してしまうので、元の変数の値や関数を使うことができなくなります。ご注意くださいませ。
open はストラクチャの中で使うと便利です。このとき、注意点が一つあります。次の例を見てください。
structure Foo = struct
val foo = "foo"
end
structure Bar = struct
open Foo
val bar = foo
end
ストラクチャ Bar は、ストラクチャ Foo を open して変数 foo の値を参照しています。実際に SML/NJ で定義すると、次のように表示されます。
structure Foo : sig val foo : string end
structure Bar :
sig
val bar : string
val foo : string
end
Bar のシグネチャには 2 つの変数 bar と foo があります。Foo をオープンしたため、Foo 内で定義された変数や関数も Bar.foo のように参照することができます。つまり、Bar をオープンすると、いっしょに Foo もオープンされてしまうのです。
このような場合、local を使うと Foo を非公開にすることができます。次の例を見てください。
structure Baz = struct
local
open Foo
in
val baz = foo
end
end
ストラクチャ Baz の中で、local を使って Foo をオープンします。変数 baz の定義では foo を参照することができますが、foo は外部に公開されません。実際に SML/NJ で定義すると、次のようになります。
structure Baz : sig val baz : string end
Baz のシグネチャで公開されているのは変数 baz だけで、変数 foo は非公開になります。
●ファンクタの引数
ところで、ストラクチャ IntQueue はシグネチャ INTQUEUE を使って Queue の型を指定しました。ファンクタを使うともっと簡単に Queue の型を指定することができます。ファンクタの引数はストラクチャだけではなく、type や val などの宣言的な要素を受け取ることができます。また、複数のストラクチャも受け取ることができます。ファンクタの一般形を示します。
(1) functor name(structure Sa: S1; structure Sb: S2; val x: int; val y: real ... ) = struct
.....
end
(2) functor name(structure Sa: S1 and Sb: S2; val x: int and y: real; ... ) = struct
.....
end
ファンクタに複数の引数を渡す場合はセミコロン ( ; ) で区切ります。この場合、ストラクチャは structure と明示します。Sa がストラクチャ名で S1 がシグネチャ名です。val x: int と val y: real のように、変数 x と y を渡すこともできます。また、(2) のように and を使って同じ宣言をつなぐこともできます。これらの方式は、今まで説明したストラクチャを一つ渡す方式 "functor name( ストラクチャ: シグネチャ )" と混在させることはできません。ご注意くださいませ。
ファンクタを呼び出す場合、引数は次のように指定します。
(1) name( structure Sa = StructA; structure Sb = StructB; val x = 1; val y = 2.0 )
(2) name( structure Sa = StructA and Sb = structB; val x = 1 and y = 2.0 )
ストラクチャは "sturcture 引数名 = ストラクチャ名" で指定します。引数名はファンクタで指定したものと同じです。ストラクチャ名のところは struct ... end で記述することもできます。変数は "val 引数名 = 値" で指定します。一般に、ファンクタで "宣言 引数名" で指定した場合、呼び出し時の指定は "宣言 引数名 = 値" となります。
ストラクチャ Queue の型はファンクタの引数に type を指定することで実現できます。次のリストを見てください。
リスト : ファンクタでデータ型を指定する (1)
functor makeQueue(type item) : sig
type 'a queue
val create : item queue
val dequeue : item queue -> item queue
val enqueue : item queue * item -> item queue
val front : item queue -> item
val isEmpty : item queue -> bool
end
= struct
datatype 'a queue = Q of 'a list * 'a list
exception EmptyQueue
val create = Q(nil, nil)
fun enqueue(Q(front, rear), x) = Q(front, x::rear)
fun dequeue(Q(nil, nil)) = raise EmptyQueue
| dequeue(Q(nil, rear)) = dequeue( Q(rev rear, nil) )
| dequeue(Q(x::xs, rear)) = Q(xs, rear)
fun front(Q(nil, nil)) = raise EmptyQueue
| front(Q(nil, rear)) = front( Q(rev rear, nil) )
| front(Q(x::xs, _)) = x
fun isEmpty(Q(nil, nil)) = true
| isEmpty(Q(_, _ )) = false
end
ファンクタはストラクチャの一種なので、ファンクタにシグネチャを指定することができます。シグネチャ sig ... end の中では、ファンクタの引数を参照することができます。ファンクタで生成されたストラクチャのシグネチャは、ファンクタで指定したシグネチャになります。したがって、ファンクタの引数 item に int を指定すれば、シグネチャの item は int になり、キューに格納されるデータは int になります。
それでは、簡単な実行例を示します。
- structure IntQueue = makeQueue(type item = int);
structure IntQueue :
sig
datatype 'a queue = ...
val create : item queue
val dequeue : item queue -> item queue
val enqueue : item queue * item -> item queue
val front : item queue -> item
val isEmpty : item queue -> bool
end
- val a = IntQueue.create;
val a = Q ([],[]) : int IntQueue.queue
ファンクタ makeQueue に type item = int を与えてストラクチャ IntQueue を生成します。create でキューを生成すると、キューに格納するデータ型が int になっていることがわかります。
また、次のように create でキューのデータ型を指定する方法もあります。この場合、シグネチャを定義しなくても動作します。
リスト : ファンクタでデータ型を指定する (2)
functor makeQueue(type item) = struct
abstype 'a queue = Q of 'a list * 'a list with
exception EmptyQueue
val create = Q(nil: item list, nil: item list)
fun enqueue(Q(front, rear), x) = Q(front, x::rear)
fun dequeue(Q(nil, nil)) = raise EmptyQueue
| dequeue(Q(nil, rear)) = dequeue( Q(rev rear, nil) )
| dequeue(Q(x::xs, rear)) = Q(xs, rear)
fun front(Q(nil, nil)) = raise EmptyQueue
| front(Q(nil, rear)) = front( Q(rev rear, nil) )
| front(Q(x::xs, _)) = x
fun isEmpty(Q(nil, nil)) = true
| isEmpty _ = false
end
end
create で nil のデータ型を item list に指定しています。これでキューに格納されるデータ型は item になります。
簡単な実行例を示します。
- structure IntQueue = makeQueue(type item = int);
structure IntQueue :
sig
exception EmptyQueue
val create : item <resultStr>.queue
val enqueue : 'a <resultStr>.queue * 'a -> 'a <resultStr>.queue
val dequeue : 'a <resultStr>.queue -> 'a <resultStr>.queue
val front : 'a <resultStr>.queue -> 'a
val isEmpty : 'a <resultStr>.queue -> bool
type 'a queue
end
- val a = IntQueue.create;
val a = - : int IntQueue.queue
このように、int を格納するキューを生成することができます。
●配列によるキューの実装
ところで、キューは配列を使っても簡単に実現することができます。SML/NJ の場合、配列を使う機会はあまりないと思うので、配列を使ったプログラムの例題としてキューを作ってみましょう。
配列を使ってキューを実装する場合、先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。
図 : キューの動作
最初、キューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値を +1 します。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。
次に、データを取り出す場合、front の示すデータを取り出しから front の値を +1 します。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。
rear, fornt ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾が繋がっているリング状と考え、rear, front が配列の範囲を超えたら 0 に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、配列を使ってキューを実現する場合は、リングバッファとするのが普通です。
●プログラムの作成
それでは実際にプログラムを作ってみましょう。最初に、基本的な操作関数を説明します。
- val clear : 'a queue -> unit
キューを空にする。
- val create : int -> item queue
指定した大きさのキューを作る。
- val dequeue : 'a queue -> 'a
キューからデータを取り出して返す。
- val enqueue : 'a queue * 'a -> unit
キューにデータを追加する。
- val front : 'a queue -> 'a
キューの先頭データを返す。データはキューから削除されない。
- val isEmpty : 'a queue -> bool
キューが空の場合は true を、そうでなければ false を返す。
- val isFull : 'a queue -> bool
キューが満杯の場合は true を、そうでなければ false を返す。
- val length : 'a queue -> int
キューに格納されたデータ数を返す。
次に、キューを生成するファンクタを定義します。次のリストを見てください。
リスト : ファンクタの定義
functor makeQueue(type item; val init: item) = struct
abstype 'a queue = Q of {front: int ref, rear: int ref,
count: int ref, size: int, buff:'a array} with
exception Queue
fun create n = Q{front = ref 0, rear = ref 0, count = ref 0, size = n,
buff = Array.array(n, init)}
・・・・・操作関数の定義・・・・・
end
end
ファンクタの引数 type item でキューに格納するデータ型を指定します。配列は関数 array で作成しますが、このとき配列の大きさと初期値が必要になります。大きさはキューを生成する関数 create の引数で指定することにし、配列の初期値はファンクタの引数 val init: item で指定することにします。
キューはレコードを使って定義します。count はキューに格納されたデータ数をカウントします。この変数を用意することで、キューの状態を簡単にチェックすることができます。front, rear, count は値を書き換えるので ref 変数で定義します。size はキューの大きさを表します。buff がキューの本体（配列）です。
関数 create はキューを生成します。引数 n がキューの大きさです。front, rear, count を 0 に初期化し、size を n に初期化します。あとは Array.array(n, init) で配列を生成するだけです。
次はデータを追加する enqueue を作ります。
リスト : キューにデータを追加する
fun enqueue(Q{rear, count, size, buff, ...}, data) =
if !count >= size then raise Queue
else (
Array.update(buff, !rear, data);
rear := !rear + 1;
count := !count + 1;
if !rear >= size then rear := 0 else ())
最初に count と size を比較して、キューが満杯かチェックします。そうであれば、例外 Queue を送出します。データは rear の位置に格納し、count と rear の値を更新します。そして、rear の値が配列の範囲を超えたならば 0 に戻します。
次は、キューからデータを取り出す関数 dequeue を作ります。
リスト : キューからデータを取り出す
fun dequeue(Q{front, count, size, buff, ...}) =
if !count = 0 then raise Queue
else Array.sub(buff, !front) before (
front := !front + 1;
count := !count - 1;
if !front >= size then front := 0 else ())
まず、キューにデータがあるか count の値をチェックします。キューが空の場合は例外 Queue を送出します。データがある場合は関数 sub で front の位置にあるデータを取り出します。before を使っているので、sub で取り出したデータが dequeue の返り値になることに注意してください。あとは、count と front の値を更新し、front の値が配列の範囲を超えたら 0 に戻します。
あとの操作関数は簡単なので説明は省略します。リストをお読みくださいませ。
リスト : キューの操作関数
fun front(Q{front=top, count, buff, ...}) =
if !count = 0 then raise Queue
else Array.sub(buff, !top)
fun clear(Q{count, front, rear, ...}) = (count := 0; front := 0; rear := 0)
fun length(Q{count, ...}) = !count
fun isEmpty(Q{count, ...}) = !count = 0
fun isFull(Q{count, size, ...}) = !count = size
●使用例
これでプログラムは完成です。それでは、簡単な使用例を示しましょう。
- structure IntQueue = makeQueue( type item = int; val init = 0 )
structure IntQueue :
sig
exception Queue
val create : int -> item <resultStr>.queue
val enqueue : 'a <resultStr>.queue * 'a -> unit
val dequeue : 'a <resultStr>.queue -> 'a
val front : 'a <resultStr>.queue -> 'a
val clear : 'a <resultStr>.queue -> unit
val length : 'a <resultStr>.queue -> int
val isEmpty : 'a <resultStr>.queue -> bool
val isFull : 'a <resultStr>.queue -> bool
type 'a queue
end
- val q = IntQueue.create 10;
val q = - : int IntQueue.queue
- app (fn x => IntQueue.enqueue(q,x)) [0,1,2,3,4,5,6,7,8,9];
val it = () : unit
- while not(IntQueue.isEmpty(q)) do print(Int.toString(IntQueue.dequeue(q))^"\n");
0
1
2
3
4
5
6
7
8
9
val it = () : unit
create でキューを作成して変数 q にセットします。app でキューにデータを 10 個セットします。これでキューは満杯になるので、これ以上データを追加することはできません。次に、dequeue でデータを取り出します。先に入れたデータから順番に取り出されていることがわかりますね。これでキューは空の状態になります。
●プログラムリスト
リスト : 配列によるキューの実装
functor makeQueue(type item; val init: item) = struct
abstype 'a queue = Q of {front: int ref, rear: int ref,
count: int ref, size: int, buff:'a array} with
exception Queue
fun create n = Q{front = ref 0, rear = ref 0, count = ref 0, size = n,
buff = Array.array( n, init )}
fun enqueue(Q{rear, count, size, buff, ...}, data) =
if !count >= size then raise Queue
else (
Array.update( buff, !rear, data );
rear := !rear + 1;
count := !count + 1;
if !rear >= size then rear := 0 else ())
fun dequeue(Q{front, count, size, buff, ...}) =
if !count = 0 then raise Queue
else Array.sub(buff, !front) before (
front := !front + 1;
count := !count - 1;
if !front >= size then front := 0 else ())
fun front(Q{front=top, count, buff, ...}) =
if !count = 0 then raise Queue
else Array.sub( buff, !top )
fun clear(Q{count, front, rear, ...}) = (count := 0; front := 0; rear := 0)
fun length(Q{count, ...}) = !count
fun isEmpty(Q{count, ...}) = !count = 0
fun isFull(Q{count, size, ...}) = !count = size
end
end
初版 2005 年 6 月 11 日
改訂 2020 年 8 月 9 日
