パターンは Common Lisp の cond や case のような条件分岐にも使うことができます。SML/NJ には case 式が用意されています。
case expr of pat1 => expr1 | pat2 => expr2 | ..... | patN => exprN
pat はパターン (pattern) のことです。pat => expr を「規則」といい、複数の規則を縦線 ( | ) でつないだものを「照合」といいます。最初に case は式 expr を評価します。その結果とマッチングするパターンの規則を選択し、対応する式を評価します。そして、その結果が case 式の返り値となります。
なお、一度規則が選択されたら、それ以降の規則は選択されません。それから、規則の式 expr1, ..., exprN の返り値は同じデータ型でなければいけません。ご注意ください。
簡単な例を示します。
- fun foo n = = case n = of 0 => print "0\n" = | 1 => print "1\n" = | _ => print "other\n"; val foo = fn : int -> unit - foo 0; 0 val it = () : unit - foo 1; 1 val it = () : unit - foo 2; other val it = () : unit
匿名変数はどんな値でもマッチングします。したがって、他の規則が選択されない場合でも、最後の規則は必ず選択されることになります。
case 式のパターンには変数を使うことができます。変数は局所変数として扱われ、有効範囲は対応する規則の式の中だけになります。たとえば、リストの要素を削除する関数 remove_if を case を使って記述すると次のようになります。
リスト : 関数 remove_if
fun remove_if(f, x) =
case x
of nil => nil
| y::ys => if f y then remove_if(f, ys)
else y :: remove_if(f, ys)
実行例を示します。
val remove_if = fn : ('a -> bool) * 'a list -> 'a list
- remove_if(fn x => x mod 2 = 0, [1,2,3,4,5,6] ); val it = [1,3,5] : int list
このように、関数の定義とよく似た形式になります。実をいうと、SML/NJ は照合を使って関数を定義することができるのです。
fun を使わずに関数 f を定義する場合、照合を使って次のように行います。
val rec f = fn pat1 => expr1 | pat2 => expr2 | ... | patN => exprN
照合による関数の定義は匿名関数と同じ形式です。匿名関数は規則が一つしかない特別な場合に相当します。rec は再帰呼び出しをする場合に限り必要になります。たとえば、関数 remove_if は次のようになります。
リスト : 関数 remove_if
val rec remove_if = fn
(_, nil) => nil |
(f, x::xs) => if f x then remove_if(f, xs)
else x::remove_if(f, xs);
実行例を示します。
val remove_if = fn : ('a -> bool) * 'a list -> 'a list
- remove_if( fn(x) => x mod 2 = 0, [1,2,3,4,5,6] ); val it = [1,3,5] : int list
このように、照合を使っても関数を定義することができます。一般的には、fun を使って関数を定義した方が簡単だと思います。
パターン x::xs を使うとリストを分解することができますが、分解した値 x や xs だけではなく、元のリストの値を参照したいときがあります。このような場合、as を使うと変数とパターンを同時に設定することができます。
識別子 as パターン
たとえば、a as x::xs と [1, 2, 3] をマッチングさせると、次のようになります。
a -> [1, 2, 3] x -> 1 xs -> [2, 3]
このように、パターン x::xs とマッチングした場合、変数 a の値は分解する前の [1, 2, 3] になります。
それでは簡単な例題として、「挿入ソート (insert sort)」を作ってみましょう。挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、リスト [2, 4, 6] に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。
ソートするリストは、tl で分解していくと空リストになります。これをソート済みのリストと考えて、ここにデータを挿入していきます。データを比較する関数は引数として渡せばいいでしょう。プログラムは次のようになります。
リスト : 挿入ソート
fun insert_sort(_, nil) = nil
| insert_sort(f, y::ys) =
let
fun insert_element(n, nil) = [n]
| insert_element(n, a as x::xs) =
if f(n, x) then n::a else x::insert_element(n, xs)
in
insert_element(y, insert_sort(f, ys))
end
関数 insert_sort は引数のリストを再帰呼び出しで分解します。insert_sort を再帰呼び出ししてリスト ys をソートし、そのリストに先頭要素 y を関数 insert_element で挿入します。
関数 insert_element は再帰呼び出しでリストをたどり、データ n を挿入する位置を探します。述語 f の返り値が真であれば、その位置にデータを挿入します。ここで、a as x::xs の変数 a を使っています。n::a とすることでリストに n を挿入することができます。
それでは実行してみましょう。
val insert_sort = fn : ('a * 'a -> bool) * 'a list -> 'a list
- insert_sort(op <, [9, 1, 8, 2, 7, 3, 6, 4, 5]); val it = [1,2,3,4,5,6,7,8,9] : int list
挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。
今まで例題としてクイックソートと挿入ソートを取り上げました。データ数を N とすると、挿入ソートの実行時間は N2 に比例します。挿入ソートは遅いソートですが、クイックソートは高速なソートで、実行時間は N * log2 N に比例します。ところがクイックソートにも弱点があり、枢軸の選び方によっては実行時間が N2 に比例する「遅いソート」になってしまいます。リストの場合、枢軸を自由に選ぶことが難しいので、クイックソートはリスト向きのアルゴリズムとはいえません。
そこで、今回はリストに適したソートアルゴリズムである「マージソート (merge sort)」を取り上げます。データ数を N とすると、マージソートの実行時間は N * log2 N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。ただし、クイックソートと違って、データによって性能が劣化することはありません。どのようなデータに対しても力を発揮してくれます。
まず最初にマージから説明します。マージ (併合) とは、複数のソート済みのリストを一つのソート済みのリストにまとめる操作です。次の図を見てください。
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
┌─ [1, 3, 5] : リスト a
[] ←┤
└─ [2, 4, 6] : リスト b
小さい方をセットする
┌─ [3, 5] : リスト a
[1] ←┘
[2, 4, 6] : リスト b
1 をセットする
[3, 5] : リスト a
[1, 2] ←┐
└─ [4, 6] : リスト b
2 をセットする
データがなくなるまで繰り返す
図 : リストのマージ
それでは、実際にプログラムを作ってみましょう。次のリストを見てください。
リスト : リストのマージ fun merge(_, nil, n) = n | merge(_, m, nil) = m | merge(f, m as x::xs, n as y::ys) = if f(x, y) then x::merge(f, xs, n) else y::merge(f, m, ys)
関数 merge の引数 f がデータを比較する述語、m と n がマージするリストです。最初の定義はリスト m が空リストになった場合で、リスト n をそのまま返します。2 番目の定義はリスト n が空リストになった場合で、リスト m をそのまま返します。この 2 つが再帰呼び出しの停止条件になります。
リスト m と n にデータがあれば、先頭要素 x と y を述語 f で比較します。f が真であれば x を、そうでなければ y を merge が返すリストに追加します。merge を再帰呼び出しするときは、追加する先頭要素をリストから取り除くことに注意してください。これでリストをマージすることができます。
簡単な実行例を示しましょう。
- merge(op <, [1, 3, 5, 7], [2, 4, 6, 8]); val it = [1,2,3,4,5,6,7,8] : int list - merge(op <, [10, 20, 30], [1, 2, 3, 4]); val it = [1,2,3,4,10,20,30] : int list
マージソートは、このマージを使ってデータをソートします。次の図を見てください。
9 5 3 7 6 4 2 8 最初の状態
|5 9|3 7|4 6|2 8| 長さ２の列に併合
|3 5 7 9|2 4 6 8| 長さ４の列に併合
2 3 4 5 6 7 8 9 ソート終了
図 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。
実際にプログラムを作る場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。
再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。
リスト : マージソート
fun merge_sort(_, nil, _) = nil
| merge_sort(_, x::xs, 1) = [x]
| merge_sort(f, x1::x2::xs, 2) =
if f(x1, x2) then [x1, x2] else [x2, x1]
| merge_sort(f, x, n) =
let
val m = n div 2
in
merge(f, merge_sort(f, x, m),
merge_sort(f, List.drop(x, m), n - m))
end
関数 merge_sort の引数 f がデータを比較する述語、x がソートするリスト、n がリストの長さを表します。merge_sort はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。
引数 x
｜
｜←── 長さn ──→｜
（１ ２ ３ ４ ５ ６ ７ ８）
｜←n/2→｜ ｜←n/2→｜
｜ ｜
引数 x 引数 y 再帰呼び出し
図 : リストの分割
merge_sort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は x と n / 2 で表し、後半部分を y と n / 2 で表します。y はリスト x の先頭から n / 2 個の要素を取り除けば求めることができます。この処理は SML/NJ に用意されている関数 drop を使うと簡単です。
List.drop(list, n)
drop は list の先頭から n 個の要素を取り除きます。list に対して n 回だけ tl を適用すると考えてもかまいません。簡単な例を示しましょう。
- List.drop( [1,2,3,4], 0 ); val it = [1,2,3,4] : int list - List.drop( [1,2,3,4], 2 ); val it = [3,4] : int list - List.drop( [1,2,3,4], 4 ); val it = [] : int list
あとは再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。リストの長さが 2 の場合は簡単なので、2 つの要素を比較してソート済みのリストを作成して返します。そして、merge_sort の返り値を merge でマージすればいいわけです。
それでは実行してみましょう。
- merge_sort(op <, [5,9,1,8,2,7,3,6,4], 9); val it = [1,2,3,4,5,6,7,8,9] : int list - merge_sort(op >, [5,9,1,8,2,7,3,6,4], 9); val it = [9,8,7,6,5,4,3,2,1] : int list
正常に動作していますね。