M.Hiroi's Home Page

Functional Programming

お気楽 Standard ML of New Jersey 入門

[ PrevPage | SML/NJ | NextPage ]

モジュール (1)

「モジュール (module)」は、データ構造とそれを操作する関数を一つにまとめるための仕組みです。最近は、モジュールに相当する機能を持つプログラミング言語が多くなりました。SML/NJ の場合、モジュールに相当する機能が「ストラクチャ (structure)」です。

●スタックとは?

簡単な例として「スタック (stack)」というデータ構造を考えてみましょう。次の図を見てください。


                  図 : スタックの動作例

上図は、バネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもう一つ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。一つ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。

この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。

●スタックの定義

SML/NJ の場合、スタックはリストを使って簡単に実現することができます。データを追加するときはリストの先頭に追加し、データを取り出すときはリストの先頭から行うように操作を限定すると、それはスタックの動作と同じになります。

最初はストラクチャを使わずにプログラムを作ります。次のリストを見てください。

リスト : スタック

(* 例外 *)
exception Stack

(* スタックの定義 *)
datatype 'a stack = S of 'a list

(* 空のスタック *)
val create = S nil

(* データの追加 *)
fun push(S x, data) = S (data::x)  

(* データの削除 *)
fun pop(S nil) = raise Stack  
|   pop(S (_::xs)) = S xs

(* データの取得 *)
fun top(S nil) = raise Stack
|   top(S (x::_)) = x

(* スタックは空か *)
fun isEmpty(S nil) = true
|   isEmpty(S _ )  = false

最初に datatype でスタック 'a stack を定義します。空のスタックを返す create は関数ではなく変数として定義します。この理由は後で説明します。スタックの操作関数は簡単です。push はデータをリストの先頭に追加します。pop はリストの先頭要素を取り除きます。データの取得は関数 top で行います。スタックが空の場合、pop と top を適用することができないので、例外 Stack を送出します。関数 isEmpty はスタックが空かチェックする述語です。

簡単な使用例を示します。

- val a0 = create;
val a0 = S [] : 'a stack
- val a1 = push(a0, 1);
val a1 = S [1] : int stack
- val a2 = push(a1, 2);
val a2 = S [2,1] : int stack
- top a2;
val it = 2 : int
- val a3 = pop a2;
val a3 = S [1] : int stack
- isEmpty a3;
val it = false : bool
- val a4 = pop a3;
val a4 = S [] : int stack
- isEmpty a4;
val it = true : bool

正常に動作していますね。関数型言語の場合、変数の値を書き換えることができないので、push や pop の返り値を別の変数に格納する必要があります。このとき、参照型の変数にスタックを格納すれば、値を書き換えることができるので便利なように思います。ところが、多相的なデータは参照にすることができません。

実をいうと、ML (SML/NJ や Ocaml など) の多相性には制限があるのです。create が関数ではなく変数なのも、多相性が制限されているからです。これはあとで説明します。

●ストラクチャの定義

それでは、ストラクチャを使ってスタックを定義してみましょう。ストラクチャの定義は次のようになります。

structure 名前 = struct
  .....
end

struct ... end がストラクチャの本体です。この間にプログラムを書きます。そこで定義された変数、関数、例外はストラクチャに属します。structure を使うとストラクチャに名前を付けることができます。ストラクチャ名を Stack とすると、プログラムは次のようになります。

リスト : ストラクチャ 

structure Stack = struct
  (* 例外 *)
  exception Stack

  (* スタックの定義 *)
  datatype 'a stack = S of 'a list

  (* 空のスタック *)
  val create = S nil

  (* データの追加 *)
  fun push(S x, data) = S (data::x)  

  (* データの削除 *)
  fun pop(S nil) = raise Stack  
  |   pop(S (_::xs)) = S xs

  (* データの取得 *)
  fun top(S nil) = raise Stack
  |   top(S (x::_)) = x

  (* スタックは空か *)
  fun isEmpty(S nil) = true
  |   isEmpty(S _ )  = false
end

SML/NJ の場合、ストラクチャ名は英大文字で始める習慣があります。struct と end の間にスタックのプログラムを書いただけです。とても簡単ですね。実際に Stack を定義すると次のように表示されます。

structure Stack :
  sig
    exception Stack
    datatype'a stack = S of 'a list
    val create : 'a stack
    val push : 'a stack * 'a -> 'a stack
    val pop : 'a stack -> 'a stack
    val top : 'a stack -> 'a
    val isEmpty : 'a stack -> bool
  end

sig ... end を「シグネチャ (signature)」といいます。シグネチャはストラクチャの仕様を記述するものです。ストラクチャを定義するとシグネチャが生成されますが、ユーザがシグネチャを定義して、それをストラクチャに設定することもできます。シグネチャは次節で詳しく説明します。

それでは実行してみましょう。

- val a0 = Stack.create;
val a0 = S [] : 'a Stack.stack
- val a1 = Stack.push(a0, 10);
val a1 = S [10] : int Stack.stack
- Stack.top a1;
val it = 10 : int
- Stack.isEmpty a1;
val it = false : bool
- val a2 = Stack.pop a1;
val a2 = S [] : int Stack.stack
- Stack.isEmpty a2;
val it = true : bool

ストラクチャで定義された変数や関数は、Stack.create のように「ストラクチャ名 + ドット ( . ) + 名前」でアクセスすることができます。

●シグネチャの使い方

シグネチャの定義は次のようになります。

signature 名前 = sig
  .....
end

sig ... end がシグネチャの本体です。この間にストラクチャの仕様を書きます。signature を使うとシグネチャに名前を付けることができます。主な仕様は次のように記述します。

シグネチャはストラクチャの仕様を記述したものですが、外部とのインターフェースの役割も持っています。たとえば、ストラクチャの内部だけで使用する変数や関数は、外部から使われることがないように隠した方がよいでしょう。このような場合、外部に公開する関数や変数だけをシグネチャに記述すればよいのです。シグネチャに記述されていない変数や関数は非公開となり、外部からアクセスすることができなくなります。

シグネチャにはもう一つ重要な機能があります。それはストラクチャの「型」としての機能です。たとえば、ストラクチャ Stack の型は 'a Stack.stack という多相型になります。データ型を特定したい場合、シグネチャに記述することで実現できます。簡単な例として、整数を格納するストラクチャ IntStack を作ってみましょう。次のプログラムを見てください。

リスト : シグネチャ

signature INTSTACK = sig
  type 'a stack
  exception Stack
  val create : int stack
  val push : int stack * int -> int stack  
  val pop : int stack -> int stack
  val top : int stack -> int
  val isEmpty : int stack -> bool
end

structure IntStack: INTSTACK = Stack

IntStack のシグネチャ INTSTACK を定義します。SML/NJ の場合、シグネチャの名前を英大文字で記述する習慣があります。type で指定するデータ型は Stack のデータ型 'a stack になります。そして、関数と変数の仕様を 'a stack から int stack に変更します。これで IntStack の仕様になります。

ストラクチャにシグネチャを指定する場合、ストラクチャ名の後ろにコロン ( : ) を付けて、その後ろにシグネチャを指定します。SML/NJ の場合、変数の型を指定するときは "変数名 : 型式" で行いました。シグネチャはストラクチャの型を表すので、"ストラクチャ名 : シグネチャ" でシグネチャを指定することができます。これで、データ型を int に特定した IntStack を生成することができます。

この他にも、シグネチャの指定方法はいくつかあります。また、シグネチャに名前を付けずに指定することもできます。簡単な例を示します。

structure Foo : sig ... end = struct ... end
structure Foo = struct ... end : sig ... end

コロン ( : ) の後ろにシグネチャを指定するところは、どの方法でも同じです。

それでは、実際に IntStack を実行してみましょう。

- val a0 = IntStack.create;
val a0 = S [] : int Stack.stack
- val a1 = IntStack.push(a0, 10);
val a1 = S [10] : int Stack.stack
- val a2 = IntStack.pop a1;
val a2 = S [] : int Stack.stack

IntStack.create のデータ型が int Stack.stack になっていますね。このように、シグネチャを使ってデータ型を特定したストラクチャを作ることができます。

●補足1 : 多相性の制限

たとえば、空リスト nil の参照を考えてみましょう。実際に ref nil で参照を生成すると次のようになります。

- val a = ref nil;
stdIn:3.5-3.16 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)

val a = ref [] : ?.X1 list ref

このように、'a list のような多相的な型ではなく、ダミーな型が割り当てられます。もしも、'a list のような多相的な型の参照を許すと、次のような代入操作が可能になります。

val a = ref nil      (* 型が 'a list とする *)

a := [1, 2, 3]       (* int list に書き換える *)
a := ["abc", "def"]  (* string list に書き換える *)

変数 a の型が int list から string list に変わってしまいます。つまり、プログラムの実行中に変数の型が変化する可能性があるわけです。SML/NJ はコンパイル時にデータ型を厳密にチェックするプログラミング言語です。実行中にデータ型が変化するような処理は、SML/NJ には想定外のことです。参照を使う場合は多相性を制限する必要があるのです。

実際にはもう少し制限が厳しくて、変数に「値」を束縛するときに限り、多相性を許すようになっています。参考文献 [1] によると、これを「値多相」といいます。この場合の「値」とは、変数、定数、関数定義、要素が値の組やレコードなどです。逆に、関数や ref の適用、if など評価が行われる式は「値」になりません。次の例を見てください。

- fun foo() = nil;
val foo = fn : unit -> 'a list

- val a = nil;
val a = [] : 'a list
- val b = foo();
stdIn:15.1-15.14 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
val b = [] : ?.X1 list

関数 foo は nil を返します。val a = nil の場合、変数 a の型は 'a list になりますが、val b = foo() は右辺が関数適用なので、変数 b の型は 'a list にはなりません。

-- 参考文献 --------
[1] Objective Caml 入門 (PDF), (五十嵐淳さん)

●補足2 : 参照を使ったスタックの実装例

ところで、シグネチャでデータ型を決定すれば、スタックを参照型の変数に格納することができます。次のリストを見てください。

リスト : スタック

structure Stack = struct
  exception Stack

  datatype 'a stack = S of 'a list

  fun create() = ref(S nil)

  fun push(x as ref(S y), data) = x := S(data::y)

  fun pop(ref(S nil)) = raise Stack
  |   pop(x as ref(S (y::ys))) = y before (x := S ys)  

  fun top(ref(S nil)) = raise Stack
  |   top(ref(S (x::_ ))) = x

  fun isEmpty(ref(S nil)) = true
  |   isEmpty(ref(S _ ))  = false
end

create は空のスタックの参照を返す関数として定義します。操作関数はスタックを格納した参照型の変数を受け取ります。この変数を書き換えることで、スタックを操作することができます。つまり、「値渡し」ではなく「参照渡し」になります。

関数 pop は仕様を変更して、取り除いたデータを返すことにします。pop で使っている演算子 befor は Common Lisp の関数 prog1 と同じ働きをします。

expr1 before expr2
- op before;
val it = fn : 'a * unit -> 'a

before は expr1 を評価し、その次に expr2 を評価します。そして、expr1 の評価結果が before の値になります。expr2 の返り値はユニットでなければいけません。before は変数の値を取り出しておいてから、変数の値を更新する処理などで役に立ちます。pop の場合、スタックの先頭データを求め、その後でスタックからデータを取り除きます。この処理は before を使うと簡単に実現できます。

次はシグネチャを定義してストラクチャ IntStack を作ります。プログラムは次のようになります。

リスト : シグネチャの定義

signature INTSTACK = sig
    type 'a stack
    exception Stack
    val create : unit -> int stack ref
    val isEmpty : int stack ref -> bool
    val pop : int stack ref -> int
    val push : int stack ref * int -> unit  
    val top : int stack ref -> int
end

structure IntStack : INTSTACK = Stack

データ型を決めているだけなので、難しいところないと思います。それでは、実行例を示します。

- val a = IntStack.create();
val a = ref (S []) : int Stack.stack ref

- IntStack.push(a,10);
val it = () : unit
- a;
val it = ref (S [10]) : int Stack.stack ref
- IntStack.push(a,20);
val it = () : unit
- a;
val it = ref (S [20,10]) : int Stack.stack ref

- IntStack.pop(a);
val it = 20 : int
- a;
val it = ref (S [10]) : int Stack.stack ref

正常に動作してますね。これで、real 用のシグネチャを定義すれば、real を格納するスタックができますし、string 用のシグネチャを定義すれば、string を格納するスタックを用意することができます。


初版 2005 年 5 月 28 日
改訂 2020 年 8 月 9 日

モジュール (2)

前回はストラクチャとシグネチャを説明しました。SML/NJ のモジュール機能はこれだけではありません。もう一つ重要な機能に「ファンクタ (functor)」があります。ファンクタは引数にストラクチャを受け取り、それを使って新しいストラクチャを生成する機能です。ファンクタはストラクチャを生成するストラクチャと考えてください。今回は「二分探索木」を例題にファンクタを説明します。

まず最初に「二分探索木」から説明しましょう。二分探索木を理解されている方は読み飛ばしてもらってかまいません。

次へ

●二分探索木

あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに検索してもなんとかなりますが、データ数が多くなると検索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。二分探索木はその名が示すように「木構造」の一種です。まずは木構造から説明しましょう。

●木構造

「木構造 (tree structer)」は「木 (tree)」とも呼ばれるデータ構造で、「節 (ノード)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。


          図 1 : 一般的な木構造の一例

木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。

木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。

ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J と K の親で、J は G の子になります。J は子を持っていないので葉となります。

子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。

●二分木

とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。


                  図 2 : 二分木の一例

上図に二分木の例を示します。二分木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータを、右側の子には大きいデータが配置されるように木を構成します。

この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。

二分探索木の探索は「二分探索 (binary search)」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。

データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log 2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。

そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、赤黒木、2-3 木、B 木、B* 木などがあります。

●二分木の実装

それでは、SML/NJ で二分木を作ってみましょう。まずはモジュールを使わずにプログラムします。最初に datatype で二分木を定義します。

リスト : 二分木の定義

datatype 'a tree = Nil | Node of 'a * 'a tree * 'a tree

二分木のデータ型は 'a tree とし、節は組で表します。もちろん、レコードを使ってもかまいません。Nil が空の木を表し、Node が節を表します。組の第 1 要素が二分木に格納するデータ、第 2 要素が左部分木、第 3 要素が右部分木を表します。簡単な例を示します。

これを図で表すと次のようになります。

●データの探索

それでは、データを探索する関数から作ってみましょう。この処理はデータを比較して左右の部分木をたどっていくだけです。

リスト : データの探索

fun search(_, Nil) = false
|   search(x, Node(y, left, right)) =
  if x = y then true
  else if x < y then search(x, left)
  else search(x, right)

関数 search の第 1 引数 x が探索するデータ、第 2 引数が二分木です。二分木が Nil であれば、これ以上探索することはできません。データは見つからなかったので false を返します。そうでなければ、引数 x と節のデータを比較します。節のデータはパターンマッチングで取り出すことができます。y がデータ、left が左部分木、right が右部分木です。x = y ならばデータが見つかったので true を返します。x < y ならば search を再帰呼び出しして左部分木をたどります。そうでなければ x > y なので右部分木をたどります。

なお、データの比較に演算子 = や < を使っているため、関数 search の型は int * int tree -> bool になります。ここで「ファンクタ」を使うと、いろいろなデータ型に対応することができます。ファンクタはあとで説明します。

●データの挿入

次は、データを挿入する関数を作りましょう。探索と同様に、データを比較して木をたどっていき、木がなくなった所に新しいデータを挿入します。

リスト : データの挿入

fun insert(x, Nil) = Node(x, Nil, Nil)
|   insert(x, T as Node(y, left, right)) =
  if x = y then T
  else if x < y then Node(y, insert(x, left), right)
  else Node(y, left, insert(x, right))

関数 insert の第 1 引数 x が挿入するデータ、第 2 引数が二分木です。二分木が Nil であれば、新しい節を作って返します。この返り値を節の部分木にセットします。

次の定義で、x と y が等しい場合は二分探索木に同じデータがあるので節をそのまま返します。x < y であれば、insert を再帰呼び出しして左部分木をたどります。そして、左部分木を insert(x, left) の返り値に置き換えた節を作って返します。もしも、left が Nil であれば、ここに新しい節が挿入され、新しい部分木が返されます。x > y であれば右部分木をたどり、データを挿入した新しい右部分木を返します。

●データの削除

次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。


               図 4 : データの削除 (葉の場合)

15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。

次に、子が一つある場合を考えてみましょう。


            図 5 : データの削除 (子が一つの場合)

16 を削除する場合、その子である 15 と置き換えれば二分木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。


            図 6 : データの削除 (子が二つの場合)

この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。たとえば、上図で 14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。

まずは木の中から最小値を探す関数と、最小値の節を削除する関数を作成しましょう。次のリストを見てください。

リスト : 最小値の探索と削除

(* 最小値を求める *)
fun search_min Nil = raise Empty
|   search_min(Node(x, Nil, _)) = x
|   search_min(Node(_, left, _)) = search_min left

(* 最小値を削除する *)
fun delete_min Nil = raise Empty
|   delete_min(Node(_, Nil, right)) = right
|   delete_min(Node(x, left, right)) = Node(x, delete_min left, right)

二分木の場合、最小値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search_min は最小値を求めてそれを返します。

最初の節はエラーチェックです。引数が空の木であれば例外を送出します。次に、左側の子の値をチェックします。もし、Nil であれば左側の子がないので、その節のデータが最小値です。格納されているデータ x を返します。そうでなければ、search_min を再帰呼び出しして左側の子をたどります。

関数 delete_min は最小値を格納している節を削除します。左側の子が Nil の節を探すのは search_min と同じです。見つけたら、もう一つの子 right を返します。そうでなければ、delete_min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を格納した新しい節を返します。これで、最小値を持つ節が削除されます。葉の場合であれば right は Nil なので、単純に削除されることになります。

それでは、データを削除する関数 delete を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。

リスト : データの削除

(* 空の木か *)
fun isEmpty Nil = true
|   isEmpty _   = false

fun delete(_, Nil) = raise Not_found
|   delete(x, Node(y, left, right)) =
  if x = y then
    if isEmpty left then right
    else if isEmpty right then left
    else Node(search_min right, left, delete_min right)
  else if x < y then Node(y, delete(x, left), right)
  else Node(y, left, delete(x, right))

まず、節が Nil ならばデータが見つからなかったので例外 Not_found を送出します。次に、削除するデータ x と節のデータ y を比較します。等しい場合はその節を削除します。left が空の木 (Nil) の場合は right を返し、right が空の木の場合は left を返します。

子が 2 つある場合は、右部分木の最小値を関数 search_min で求め、その値を格納した新しい節を作ります。このとき、関数 delete_min で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換えることができます。

x と節のデータ y が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じで、delete の返り値を格納した新しい節を返します。

-- note --------
[*1] 逆に、左部分木の中から最大値を探し、それと削除するデータを置き換えてもかまいません。

●二分木の巡回

最後に、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。

  1. 行きがけ順
    まず節のデータを出力、その後左の子、右の子の順番で出力する。
  2. 帰りがけ順
    左の子、右の子と出力してから、節のデータを出力する。
  3. 通りがけ順
    左の子を出力、次に節のデータを出力、最後に右の子を出力する。

名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。

二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理は、再帰定義を使えば簡単に実現できます。

リスト : 二分木の巡回

fun foreach _ Nil = ()
|   foreach f (Node(x, left, right)) = (foreach f left; f x; foreach f right)

関数 foreach は二分木を通りがけ順に巡回し、格納されているデータに関数 f を適用します。まず、二分木が Nil ならば何もしないで unit を返します。これが再帰呼び出しの停止条件となります。あとは通りがけ順の定義そのままにプログラムをするだけです。左部分木をたどるため、left に対して foreach を再帰呼び出しします。次に、節のデータ x に関数 f を適用します。最後に右部分木をたどるため、right に対して foreach を再帰呼び出しします。

●実行例

それでは簡単な実行例を示しましょう。

- val a0 = insert(5, Nil);
val a0 = Node (5,Nil,Nil) : int tree
- val a1 = insert(3, a0);
val a1 = Node (5,Node (3,Nil,Nil),Nil) : int tree
- val a2 = insert(7, a1);
val a2 = Node (5,Node (3,Nil,Nil),Node (7,Nil,Nil)) : int tree
- search(3, a2);
val it = true : bool
- search(0, a2);
val it = false : bool
- foreach (fn x => print (Int.toString x ^ "\n")) a2;
3
5
7
val it = () : unit
- val a3 = delete(5, a2);
val a3 = Node (7,Node (3,Nil,Nil),Nil) : int tree

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

●プログラムリスト1

(*
 * tree0.sml : 二分木
 *
 *             Copyright 2005-2020 Makoto Hiroi
 *)
(* 例外 *)
exception Empty
exception Not_found

(* 節の定義 *)
datatype 'a tree = Nil | Node of 'a * 'a tree * 'a tree

(* 空の木か *)
fun isEmpty Nil = true
|   isEmpty _   = false

(* 探索 *)
fun search(_, Nil) = false
|   search(x, Node(y, left, right)) =
  if x = y then true
  else if x < y then search(x, left)
  else search(x, right)

(* 挿入 *)
fun insert(x, Nil) = Node(x, Nil, Nil)
|   insert(x, T as Node(y, left, right)) =
  if x = y then T
  else if x < y then Node(y, insert(x, left), right)
  else Node(y, left, insert(x, right))

(* 最小値 *)
fun search_min Nil = raise Empty
|   search_min(Node(x, Nil, _)) = x
|   search_min(Node(_, left, _)) = search_min left

(* 最大値 *)
fun search_max Nil = raise Empty
|   search_max(Node(x, _, Nil)) = x
|   search_max(Node(_, _, right)) = search_max right

(* 最小値の削除 *)
fun delete_min Nil = raise Empty
|   delete_min(Node(_, Nil, right)) = right
|   delete_min(Node(x, left, right)) = Node(x, delete_min left, right)

(* 最大値の削除 *)
fun delete_max Nil = raise Empty
|   delete_max(Node(_, left, Nil)) = left
|   delete_max(Node(x, left, right)) = Node(x, left, delete_max right)

(* 削除 *)
fun delete(_, Nil) = raise Not_found
|   delete(x, Node(y, left, right)) =
  if x = y then
    if isEmpty left then right
    else if isEmpty right then left
    else Node(search_min right, left, delete_min right)
  else if x < y then Node(y, delete(x, left), right)
  else Node(y, left, delete(x, right))

(* 巡回 *)
fun foreach _ Nil = ()
|   foreach f (Node(x, left, right)) = (foreach f left; f x; foreach f right)

●ファンクタ

それではファンクタを使って、二分探索木を改良しましょう。ファンクタは次のように定義します。

functor 名前 (structA: sigA) = struct
  .....
end

ファンクタは引数に与えられたストラクチャ structA を使って新しいストラクチャを生成します。structA は関数定義の引数 (仮引数) と同じと考えてください。ファンクタは structA.func や structA.value のように、structA に定義されている関数や変数を使ってストラクチャを定義します。そして、structA の型をシグネチャ sigA で指定します。逆にいえば、ファンクタで必要になる関数や変数の仕様を sigA に記述するのです。ファンクタに与えるストラクチャは、このシグネチャの仕様を満たす必要があります。

●シグネチャの定義

二分探索木はデータを比較する関数が必要です。これをストラクチャに定義して渡すことにします。シグネチャの定義は次のようになります。

リスト : シグネチャの定義

signature ITEM = sig
  type item
  val compare : item * item -> order  
end

シグネチャの名前は ITEM としました。データの比較関数を定義するストラクチャなので、名前を ORDER にしている参考文献もあります。最初に type で item というデータ型を宣言します。このデータ型を使ってシグネチャを記述します。具体的なデータ型の指定はストラクチャで行います。データを比較する関数が compare です。関数型は item * item -> order とします。order は SML/NJ に定義されているデータ型です。

datatype order = LESS | EQUAL | GREATER

order はデータの大小関係を表します。compare(x, y) は x < y ならば LESS を、x = y ならば EQUAL を、x > y ならば GREATER を返すことにします。

●ファンクタの定義

このシグネチャを使ってファンクタを定義します。プログラムは次のようになります。

リスト : ファンクタの定義

functor makeTree(Item: ITEM) = struct
  (* 例外 *)
  exception Empty
  exception Not_found

  (* 節の定義 *)
  datatype 'a tree = Nil | Node of 'a * 'a tree * 'a tree

  (* 二分木の生成 *)
  val create = Nil : Item.item tree

  (* 空の木か *)
  fun isEmpty Nil = true
  |   isEmpty _   = false

  (* 探索 *)
  fun search(_, Nil) = false
  |   search(x, Node(y, left, right)) =
    case Item.compare(x, y)
      of EQUAL   => true 
       | LESS    => search( x, left )
       | GREATER => search( x, right )

  ・・・省略・・・

  (* 巡回 *)
  fun app _ Nil = ()
  |   app f (Node(x, left, right)) = (app f left; f x; app f right)
end

引数のストラクチャを Item としシグネチャを ITEM とします。ファンクタで指定するストラクチャ名は関数定義の仮引数と同じなので、あらかじめ Item というストラクチャを定義しておく必要はありません。ストラクチャで定義されているデータ型は Item.item で、比較関数は Item.compare で参照することができます。

二分木のデータ型は今までと同じ 'a tree です。変数 create はデータ型を Item.item tree に限定します。Nil だけだと多相的なデータになります。あとは各関数でデータを比較するときに Item.compare を呼び出します。compare は order を返すので、case で場合分けしています。最後に、二分木の要素に関数 f を適用する高階関数 foreach を app に変更します。

●ストラクチャの定義と生成

次は、ファンクタに渡すストラクチャを作ります。

リスト : ストラクチャの定義と生成

structure IntItem: ITEM = struct
  type item = int
  fun compare(x, y) =
    if x < y then LESS
    else if x = y then EQUAL
    else GREATER
end

structure IntTree = makeTree(IntItem)  

二分木に格納するデータは int で、ストラクチャの名前は IntItem とします。最初に、シグネチャで宣言した item のデータ型を int にします。type はデータ型の宣言だけではなく、データ型に名前を付ける機能があります。

type 名前 = 型式

type item = int で、シグネチャで宣言したデータ型 item は int になります。あとは関数 compare を定義するだけです。compare はシグネチャで item * item -> order と定義されているので、2 つの整数値を引数に受け取る関数になります。最後に、int を格納する二分木 IntTree をファンクタで生成します。これはファンクタ makeBinTree に IntItem を渡すだけです。

それでは実際に試してみましょう。IntTree を生成すると、次のようなシグネチャが表示されます。

structure IntTree :
  sig
    exception Empty
    exception Not_found
    datatype'a tree
      = Nil | Node of 'a * 'a <resultStr>.tree * 'a <resultStr>.tree
    val create : Item.item <resultStr>.tree
    val isEmpty : 'a <resultStr>.tree -> bool
    val search : Item.item * Item.item <resultStr>.tree -> bool
    val
        insert : Item.item * Item.item <resultStr>.tree
                  -> Item.item <resultStr>.tree
    val search_min : 'a <resultStr>.tree -> 'a
    val search_max : 'a <resultStr>.tree -> 'a
    val delete_min : 'a <resultStr>.tree -> 'a <resultStr>.tree
    val delete_max : 'a <resultStr>.tree -> 'a <resultStr>.tree
    val
        delete : Item.item * Item.item <resultStr>.tree
                  -> Item.item <resultStr>.tree
    val app : ('a -> 'b) -> 'a <resultStr>.tree -> unit
  end

●実行例 (2)

IntTree の簡単な実行例を示します。

- val a = IntTree.create;
val a = Nil : IntItem.item IntTree.tree

- val a1 = IntTree.insert(10, a);
val a1 = Node (10,Nil,Nil) : IntItem.item IntTree.tree
- val a2 = IntTree.insert(5, a1);
val a2 = Node (10,Node (5,Nil,Nil),Nil) : IntItem.item IntTree.tree
- val a3 = IntTree.insert(15, a2);
val a3 = Node (10,Node (5,Nil,Nil),Node (15,Nil,Nil))
  : IntItem.item IntTree.tree

- IntTree.app (fn(x)=>print(Int.toString(x) ^ "\n")) a3;
5
10
15
val it = () : unit

- val a = List.foldr (fn(x, a) => IntTree.insert(x, a)) IntTree.create [5,4,6,7,3,2,8,9,1,0];
val a = Node (0,Nil,Node (1,Nil,Node (9,Node (8,Node (#,#,#),Nil),Nil)))
  : IntItem.item IntTree.tree
- IntTree.app (fn x => print (Int.toString x ^ " ")) a;
0 1 2 3 4 5 6 7 8 9 val it = () : unit
- IntTree.search(0, a);
val it = true : bool
- IntTree.search(5, a);
val it = true : bool
- IntTree.search(9, a);
val it = true : bool
- IntTree.search(10, a);
val it = false : bool

- IntTree.search_min(a);
val it = 0 : IntItem.item
- IntTree.search_max(a);
val it = 9 : IntItem.item
- val a1 = IntTree.delete_min(a);
val a1 = Node (1,Nil,Node (9,Node (8,Node (2,Nil,Node (#,#,#)),Nil),Nil))
  : IntItem.item IntTree.tree
- IntTree.search_min(a1);
val it = 1 : IntItem.item
- val a2 = IntTree.delete_max(a1);
val a2 = Node (1,Nil,Node (8,Node (2,Nil,Node (3,Nil,Node (#,#,#))),Nil))
  : IntItem.item IntTree.tree
- IntTree.search_max(a2);
val it = 8 : IntItem.item

- val a3 = List.foldr (fn(x, y) => IntTree.delete(x, y)) a [0,1,2,3,4,5,6,7,8,9];
val a3 = Nil : IntItem.item IntTree.tree
- IntTree.isEmpty a3;
val it = true : bool

正常に動作していますね。興味のある方はいろいろ試してみてください。

●プログラムリスト2

(*
 * tree1.sml : 二分木
 *
 *             Copyright 2005-2020 Makoto Hiroi
 *)
signature ITEM = sig
    type item
    val compare : item * item -> order  
end

functor makeTree(Item: ITEM) = struct
  (* 例外 *)
  exception Empty
  exception Not_found

  (* 節の定義 *)
  datatype 'a tree = Nil | Node of 'a * 'a tree * 'a tree

  (* 二分木の生成 *)
  val create = Nil : Item.item tree

  (* 空の木か *)
  fun isEmpty Nil = true
  |   isEmpty _   = false

  (* 探索 *)
  fun search(_, Nil) = false
  |   search(x, Node(y, left, right)) =
    case Item.compare(x, y)
      of EQUAL   => true 
       | LESS    => search( x, left )
       | GREATER => search( x, right )

  (* 挿入 *)
  fun insert(x, Nil) = Node(x, Nil, Nil)
  |   insert(x, T as Node(y, left, right)) =
    case Item.compare(x, y)
      of EQUAL   => T 
       | LESS    => Node(y, insert(x, left), right)
       | GREATER => Node(y, left, insert(x, right))

  (* 最小値 *)
  fun search_min Nil = raise Empty
  |   search_min(Node(x, Nil, _)) = x
  |   search_min(Node(_, left, _)) = search_min left

  (* 最大値 *)
  fun search_max Nil = raise Empty
  |   search_max(Node(x, _, Nil)) = x
  |   search_max(Node(_, _, right)) = search_max right

  (* 最小値の削除 *)
  fun delete_min Nil = raise Empty
  |   delete_min(Node(_, Nil, right)) = right
  |   delete_min(Node(x, left, right)) = Node(x, delete_min left, right)

  (* 最大値の削除 *)
  fun delete_max Nil = raise Empty
  |   delete_max(Node(_, left, Nil)) = left
  |   delete_max(Node(x, left, right)) = Node(x, left, delete_max right)

  (* 削除 *)
  fun delete(_, Nil) = raise Not_found
  |   delete(x, Node(y, left, right)) =
    case Item.compare(x, y)
      of EQUAL => if isEmpty left then right
                  else if isEmpty right then left
                  else Node(search_min right, left, delete_min right)
      | LESS    => Node(y, delete(x, left), right)
      | GRAETER => Node(y, left, delete(x, right))

  (* 巡回 *)
  fun app _ Nil = ()
  |   app f (Node(x, left, right)) = (app f left; f x; app f right)
end

structure IntItem: ITEM = struct
  type item = int
  fun compare(x, y) =
      if x < y then LESS
      else if x = y then EQUAL
      else GREATER
end

structure IntTree = makeTree(IntItem)  

初版 2005 年 6 月 4 日
改訂 2020 年 8 月 9 日

Copyright (C) 2005-2020 Makoto Hiroi
All rights reserved.

[ PrevPage | SML/NJ | NextPage ]