パターンは 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
匿名変数はどんな値でもマッチングします。したがって、他の規則が選択されない場合でも、最後の規則は必ず選択されることになります。
SML/NJ は照合を使っていろいろな機能を実現しています。たとえば、if-then-else は次のように case 式で表すことができます。
if E then F else G ==> case E of ture => F | false => G
パターンの定義は true と false しかありません。したがって、式 E が bool 以外のデータ型だとエラーになるわけです。
- if 1 then 1 else 0;
stdIn:13.1-13.19 Error: case object and rules don't agree [literal]
rule domain: bool
object: int
in expression:
(case 1
of true => 1
| false => 0)
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 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。
「例外 (exception) 」は主にエラー処理で使われる機能です。「例外＝エラー処理」と考えてもらってもかまいません。Common Lisp には「コンディション (condition) 」という例外処理があります。最近は例外処理を持っているプログラミング言語が多くなりました。もちろん、SML/NJ にも例外処理があります。
SML/NJ にはあらかじめ定義されている例外があります。たとえば、次の例を見てください。
- 4 div 0; uncaught exception divide by zero - tl( tl( [1] ) ); uncaught exception Empty
最初の例は 0 で除算した場合です。例外処理を何も行っていなければ、SML/NJ は処理を中断して uncaught exception と表示します。そして、その後ろに例外の種類を表示します。この場合は divide by zero という例外が発生したことがわかります。次の例は空リスト (nil) に tl を適用した場合です。この場合は Empty という例外が発生します。
なお、例外 Empty が発生したことを、「例外 Empty が送出された」という場合もあります。このドキュメントでは、「例外を送出する」とか「例外が送出された」と記述することにします。
例外は exception を使って、ユーザが独自に定義することができます。
exception 名前 exception 名前 of 型式
たとえば、exception Foo とすると例外 Foo が定義されます。SML/NJ では、例外の名前を英大文字から始める習慣があります。例外に引数を渡す場合は型式を指定します。たとえば、exception Bar of int * int とすると、例外 Bar に整数を 2 つ渡すことができます。それでは、実際に定義してみましょう。
- exception Foo; exception Foo - Foo; val it = Foo(-) : exn - exception Bar of int * int; exception Bar of int * int - Bar; val it = fn : int * int -> exn
SML/NJ の場合、例外は exn というデータ型になります。型式を指定すると、Bar は例外を返す関数として定義されます。そして、関数 Bar の返り値は例外 Bar になります。
例外を送出するには raise を使います。
raise 例外
たとえば、raise Foo とすれば例外 Foo が送出されます。raise Bar( 1, 2 ) とすれば、例外 Bar が送出されます。次の例を見てください。
- fun foo( n ) = if n < 0 then raise Foo else 1; val foo = fn : int -> int - foo( 1 ); val it = 1 : int - foo( ~1 ); uncaught exception Foo - fun bar( a, b ) = if a < 0 orelse b < 0 then raise Bar( a, b ) else 1; val bar = fn : int * int -> int - bar( 1, 1 ); val it = 1 : int - bar( 1, ~1 ); uncaught exception Bar
関数 foo( n ) は、n < 0 の場合に例外 Foo を送出し、それ以外の場合は 1 を返します。関数 bar( a, b ) は a < 0 または b < 0 の場合に例外 Bar を送出し、それ以外の場合は 1 を返します。if E then F else G は式 F と G の返り値が同じデータ型でなければいけませんが、式 F が例外を送出する raise なので、式 G の評価結果が if の値になります。
それでは簡単な例題として、階乗を求める関数 fact に引数をチェックする処理を追加してみましょう。次のリストを見てください。
リスト : 階乗
exception Negative
fun fact( n ) =
let
fun facti( 0, a ) = a
| facti( n, a ) = facti( n - 1, n * a )
in
if n < 0 then raise Negative
else facti( n, 1 )
end
最初に exception で例外 Nagative を定義します。そして、関数 facti を呼び出す前に引数 n の値をチェックします。n < 0 であれば raise で例外 Nagative を送出します。簡単な実行例を示します。
- fact( 10 ); val it = 3628800 : int - fact( ~10 ); uncaught exception Negative
SML/NJ の場合、送出された例外を「捕捉 (catch) 」することで、処理を中断せずに継続することができます。処理をやり直したい場合や特別なエラー処理を行いたい場合、例外を捕捉できると便利です。SML/NJ では、次の式で例外を捕捉することができます。
expr handle pat1 => expr1 | pat2 => expr2 | ... | patN => exprN
例外を捕捉するには handle を使います。式 expr の処理で例外が送出されると、その例外とマッチングするパターンの規則を選択し、対応する式を評価します。そして、その結果が handle の返り値となります。式 expr が正常に終了した場合は、expr の評価結果が handle の返り値になります。
簡単な例を示しましょう。次のリストを見てください。
リスト : 例外の捕捉
exception Foo of int
fun foo( n ) = if n < 0 then raise Foo( n ) else 1
fun foo1( n ) = foo( n ) handle
Foo( ~1 ) => (print "Foo error 1\n"; 0) |
Foo( ~2 ) => (print "Foo error 2\n"; 0) |
Foo( _ ) => (print "Foo error 3\n"; 0)
関数 foo は引数 n が負の場合に例外 Foo を送出します。関数 foo1 は foo を呼び出し、例外が送出された場合は handle で捕捉します。例外の引数はパターンマッチングで取り出すことができます。Foo( ~1 ) の場合は "Foo error 1" を表示して 0 を返します。関数 foo の返り値は int なので、例外を捕捉したときに評価する式の返り値も int でなければいけません。ご注意ください。
Foo( ~2 ) の場合は "Foo error 2" を表示して 0 を返します。最後のパターンは匿名変数が使われているので、その他の数値はこの規則とマッチングします。"Foo error 3" を表示して 0 を返します。
それでは、実行してみましょう。
- foo( ~1 ); uncaught exception Foo - foo1( 2 ); val it = 1 : int - foo1( ~1 ); Foo error 1 val it = 0 : int - foo1( ~2 ); Foo error 2 val it = 0 : int - foo1( ~4 ); Foo error 3 val it = 0 : int
foo( ~1 ) をそのまま評価すると例外を送出します。foo1( ~1 ) を評価すると foo が送出した例外を捕捉して、エラー処理を行ってから 0 を返しています。foo1( ~2 ) も foo1( ~4 ) も例外 Foo を捕捉しています。このように、例外を捕捉して処理を続行することができます。
SML/NJ は関数型言語なので、関数の引数や let で定義した局所変数の値を書き換えることはできません。ところが、SML/NJ では「配列」と「参照」というデータ型に限り、値を書き換えることができます。つまり、手続き型言語のように「副作用」を伴う操作を行うことができるわけです。関数型言語としては不純な機能なのですが、問題によっては配列や参照を使った方が簡単にプログラムできる場合もあります。
配列を操作する関数はストラクチャ Array に定義されています。配列の生成は関数 array を使います。
Array.array( size, init_value )
array で生成される配列は 1 次元配列です。size は配列の大きさ、init_value は初期値を指定します。簡単な例を示します。
- val a = Array.array( 8, 0 ); val a = [|0,0,0,0,0,0,0,0|] : int array - val b = Array.array( 8, true ); val b = [|true,true,true,true,true,true,true,true|] : bool array - val c = Array.array( 8, ( 0, 0 ) ); val c = [|(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0)|] : (int * int) array
SML/NJ の場合、配列は [| ... |] で表します。ただし、リストや組と違って配列の生成に [| ... |] を使うことはできません。配列の型はリストのように格納するデータ型によって決まります。int を格納する配列は int array に、bool であれば bool array に、組であれば (int * int) array になります。
配列のアクセスは関数 sub と update で行います。
Array.sub( a, n ) Ayyay,update( a, n, data )
関数 sub は第 1 引数に配列、第 2 引数に整数値（添字 : subscript）を指定します。配列の要素は 0 から数えます。関数 sub をＣ言語で書くと a[n] に相当します。次の例を見てください。
- a; val it = [|0,0,0,0,0,0,0,0|] : int array - Array.sub( a, 0 ); val it = 0 : int - Array.sub( a, 7 ); val it = 0 : int - Array.sub( a, 8 ); uncaught exception subscript out of bounds
配列 a の大きさは 8 なので、添字の範囲は 0 から 7 になります。範囲外の添字を指定すると例外が送出されます。
配列の値を書き換えるには関数 update を使います。第 1 引数が配列、第 2 引数が添字、第 3 引数が配列に代入するデータです。関数 update をＣ言語で書くと a[n] = data に相当します。次の例を見てください。
- a; val it = [|0,0,0,0,0,0,0,0|] : int array - Array.update( a, 0, 10 ); val it = () : unit - Array.update( a, 7, 17 ); val it = () : unit - a; val it = [|10,0,0,0,0,0,0,17|] : int array
このように、update は配列 a の値を書き換えます。update の返り値は unit です。
ここで、ストラクチャ Array に用意されている関数をいくつか紹介しましょう。配列の大きさは関数 length で求めることができます。
- a; val it = [|10,0,0,0,0,0,0,17|] : int array - Array.length( a ); val it = 8 : int
関数 fromList はリストを配列に変換します。
- Array.fromList( [1,2,3,4,5] ); val it = [|1,2,3,4,5|] : int array - Array.fromList( ["ab","cd","ef","gh"] ); val it = [|"ab","cd","ef","gh"|] : string array
Array には配列用の高階関数も用意されています。
val app : ('a -> unit) -> 'a array -> unit
val foldl : ('a * 'b -> 'b) -> 'b -> 'a array -> 'b
val foldr : ('a * 'b -> 'b) -> 'b -> 'a array -> 'b
val modify : ('a -> 'a) -> 'a array -> unit
val tabulate : int * (int -> 'a) -> 'a array
app, foldl, foldr は今までに説明した高階関数の配列バージョンです。関数 modify は配列の要素に関数を適用し、その結果を配列に代入します。配列の内容が書き換えられることに注意してください。つまり、結果を格納する配列を新しく生成するのではなく、引数の配列に結果を代入するのです。簡単な例を示します。
- val a = Array.fromList( [1,2,3,4,5] ); val a = [|1,2,3,4,5|] : int array - Array.modify (fn(x) => x * x) a; val it = () : unit - a; val it = [|1,4,9,16,25|] : int array
このように、modify は引数 a の配列を直接書き換えています。
関数 tabulate は整数 n と関数 f を受け取り、0 から n - 1 までの値を関数 f に適用して、その結果を格納した配列を生成します。次の例を見てください。
- Array.tabulate( 8, fn(x) => x ); val it = [|0,1,2,3,4,5,6,7|] : int array - Array.tabulate( 8, fn(x) => x * 2 ); val it = [|0,2,4,6,8,10,12,14|] : int array
ちなみに、tabulate は配列だけではありません。ストラクチャ List にはリストを生成する tabulate が用意されています。
「参照 (reference) 」はデータを間接的に参照する機能です。一般に、変数束縛は変数とデータを直接結び付けます。これに対し、参照は変数とデータを直接結び付けるのではなく、その間にデータを指し示す特別なデータ型を経由します。このデータ型を「参照型」といいます。次の図を見てください。
データ
┌───┐ ┌───┐
│変数 a│──→│ 11 │
└───┘ 束縛 └───┘
(A) 通常の束縛
参照型 データ
┌───┐ ┌──┬─┐ ┌───┐
│変数 b│──→│ref │・┼──→│ 11 │
└───┘ 束縛 └──┴─┘ └───┘
(B) 参照型データを束縛
図 : 参照 (1)
上図 (A) は通常の変数束縛です。val a = 11 とすると、変数 a に数値 11 が束縛されます。(B) が参照を図示したものです。変数 b には参照型データが束縛され、参照型データが数値 11 を指し示しています。変数 b は参照型データを経由して数値 11 を参照することができます。
SML/NJ で参照型データを生成するには ref を使います。次の例を見てください。
- val b = ref 11; val b = ref 11 : int ref - b; val it = ref 11 : int ref - val c = ref "foo"; val c = ref "foo" : string ref - c; val it = ref "foo" : string ref
ref 11 は数値 11 を指し示す参照型データを生成し、それが変数 b に束縛されます。この場合、データの型は int ref になります。ref "foo" は文字列 "foo" を指し示す string ref を生成し、それが変数 c に束縛されます。今後、参照型データを束縛した変数を「ref 変数」と呼ぶことにします。
参照先のデータを求めるには演算子 ! を使います。ref 変数 b と c に演算子 ! を適用すると、次のようになります。
- !b; val it = 11 : int - !c; val it = "foo" : string - val ref d = b; val d = 11 : int - val ref e = c; val e = "foo" : string
ref はパターンとしても使えるので、演算子 ! だけではなく、パターンマッチングでも参照先の値を取り出すことができます。
参照型データは参照するデータを変更することができます。次の図を見てください。
参照型 データ
┌───┐ ┌──┬─┐ ┌───┐
│変数 b│──→│ref │・┼ Ｘ →│ 11 │
└───┘ 束縛 └──┴┼┘ └───┘
│ ┌───┐
└───→│ 22 │
└───┘
(C) データの書き換え
図 : 参照 (2)
上図 (C) は参照するデータを数値 11 から数値 22 に変更しています。すると、ref 変数 b が参照する値は 22 になります。ようするに、ref 変数 b の値を書き換えることと同じ効果が得られるのです。ref 変数の書き換えは演算子 := で行います。次の例を見てください。
- b := 22; val it = () : unit - !b; val it = 22 : int - c := "bar"; val it = () : unit - !c; val it = "bar" : string
b := 22 とすると、ref 変数 b の値は 11 から 22 に書き換えられます。同様に、c := "bar" とすると、ref 変数 c の値は "foo" から "bar" になります。
今まで繰り返しは再帰定義を使って行いましたが、SML/NJ には簡単な繰り返しを行う while ループが用意されています。
while expr1 do expr2
while は expr1 を評価し、その結果が真の間 expr2 を繰り返し評価します。while の処理を図に示すと次のようになります。
↓
├←─────┐
偽┌─────┐ │
┌───│条件:expr1│ │
│ └─────┘ │
│ ↓真 │
│ ┌─────┐ │
│ │式 : expr2│ │
│ └─────┘ │
│ └──────┘
└──────┐
↓
図 : while の処理
図を見ればおわかりのように while はいたって単純ですが、条件が偽にならないと「無限ループ」に陥ってしまうので注意してください。while はユニットを返します。簡単な例を示しましょう。
リスト : 階乗
fun fact( n ) =
let
val i = ref n
val v = ref 1
in
while !i > 0 do (
v := !v * !i;
i := !i - 1
);
!v
end
階乗を求める関数 fact を while を使ってプログラムしました。let で ref 変数 i, v を定義し、その値を書き換えながら階乗 n * (n - 1) * ... * 2 * 1 を計算しています。最後に階乗の値 !v を返します。
もうひとつ簡単な例を示しましょう。ちょっと寄り道「組み合わせの数」 で作成した「パスカルの三角形」を while ループでプログラムしてみます。
リスト : パスカルの三角形を表示
fun pascal( x ) =
let
val n = ref 0
val r = ref 0
in
while !n <= x do (
r := 0;
while !r <= !n do (
print_int( ncr( !n, !r ) );
r := !r + 1
);
print("\n");
n := !n + 1
)
end
ref 変数 n と r を用意し、while で「二重ループ」しています。最初のループで n の値を 0 から x まで増やし、次のループで r の値を 0 から n まで増やしています。while ループで複数の式を評価する場合は複文 (expr1; expr2; ... exprN) を使ってください。
それでは実行してみましょう。
- pascal( 10 ); 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 val it = () : unit
正常に動作していますね。
今回は「組み合わせ (combination) 」を生成するプログラムを作ってみましょう。たとえば、リスト [1, 2, 3, 4, 5] の中から 3 個を選ぶ組み合わせは次のようになります。
1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5 2 3 4, 2 3 5, 2 4 5, 3 4 5
最初に 1 を選択した場合、次は [2, 3, 4, 5] の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は [3, 4, 5] の中から 1 個を選べばいいわけです。これで、[1, 2, 3], [1, 2, 4], [1, 2, 5] が生成されます。[2, 3, 4, 5] の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は [3, 4, 5] の中から 2 個を選べばいいわけです。ここで 3 を選ぶと [1, 3, 4], [1, 3, 5] が生成できます。同様に、3 を除いた [4, 5] の中から 2 個をえらぶと [1, 4, 5] を生成することができます。
これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり [2, 3, 4, 5] から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は次に示す組み合わせの公式と同じです。
nC0 = nCn = 1 nCr = n-1Cr-1 + n-1Cr
これをプログラムすると次のようになります。
リスト : 組み合わせの生成
(* 例外の定義 *)
exception Comb
(* int list の表示 *)
fun print_intlist( nil ) = print( "\n" )
| print_intlist( x::xs ) =
( print( Int.toString(x) ^ " " ); print_intlist( xs ) )
(* 組み合わせを出力 *)
fun comb( 0, _, y ) = print_intlist( rev y )
| comb( _, nil, _ ) = raise Comb
| comb( n, a as x::xs, y ) =
if length( a ) = n then print_intlist( (rev y) @ a )
else ( comb( n - 1, xs, x::y ); comb( n, xs, y ) )
関数 comb は引数 a のリストから n 個を選ぶ組み合わせを生成します。選んだ数字は第 3 引数 y のリストに格納します。n が 0 になったら組み合わせを一つ生成できたので、y を rev で逆順にして print で出力します。3 番目の定義で、リスト a の長さが n と等しくなったならば、リストの要素を全て選択します。rev で y を逆順にして演算子 @ でリスト a と結合してから print_intlist で出力します。
この 2 つの条件が再帰呼び出しの停止条件になります。これ以外で第 2 引数のリストが nil になる場合は、引数 n にリスト a の長さよりも大きな値を指定した場合です。この場合は raise で例外 Comb を送出します。
あとは関数 comb を再帰呼び出しするだけです。最初の呼び出しは先頭の要素を選択する場合です。先頭要素 x を y に追加して、リスト xs の中から n - 1 個を選びます。最後の呼び出しが先頭の要素を選ばない場合です。リスト xs の中から n 個を選びます。
簡単な実行例を示します。
- comb( 3, [1,2,3,4,5], nil ); 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 val it = () : unit
正常に動作していますね。生成した組み合わせをリストに格納して返す場合も簡単です。プログラムは次のようになります。
リスト : 組み合わせの生成 (2)
fun comb_list( n, nums ) =
let
fun comb_sub( 0, _, y, z ) = ( rev y )::z
| comb_sub( _, nil, _, _ ) = raise Comb
| comb_sub( n, a as x::xs, y, z ) =
if length( a ) = n then ( (rev y) @ a )::z
else comb_sub( n, xs, y, comb_sub( n - 1, xs, x::y, z ) )
in
comb_sub( n, nums, nil, nil )
end
関数 comb_sub は comb を改造したもので、生成した組み合わせを第 4 引数のリストに格納します。comb_sub は組み合わせを格納したリスト (第 4 引数) をそのまま返します。comb_sub を呼び出す場合、この返り値を第 4 引数に渡すことで、生成した組み合わせを格納していくことができます。具体的には、comb_sub を再帰呼び出しするところで、1 回目の呼び出しの返り値を 2 回目の呼び出しの第 4 引数に渡します。これで生成した組み合わせをリストに格納することができます。
それでは実行結果を示します。
val comb_list = fn : int * 'a list -> 'a list list
- comb_list( 3, [1, 2, 3, 4, 5] );
val it = [[3,4,5],[2,4,5],[2,3,5],[2,3,4],[1,4,5],
[1,3,5],[1,3,4],[1,2,5],[1,2,4],[1,2,3]] : int list list
正常に動作していますね。
ソートのお話です。今まで例題としてクイックソートと挿入ソートを取り上げました。データ数を N とすると、挿入ソートの実行時間は N2 に比例します。挿入ソートは遅いソートですが、クイックソートは高速なソートで、実行時間は N * log2 N に比例します。ところがクイックソートにも弱点があり、枢軸の選び方によっては実行時間が N2 に比例する「遅いソート」になってしまいます。リストの場合、枢軸を自由に選ぶことが難しいので、クイックソートはリスト向きのアルゴリズムとはいえません。
そこで、今回はリストに適したソートアルゴリズムである「マージソート (merge sort) 」を取り上げます。データ数を N とすると、マージソートの実行時間は N * log2 N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。ただし、クイックソートと違って、データによって性能が劣化することはありません。どのようなデータに対しても力を発揮してくれます。
まず最初にマージから説明します。マージ (併合) とは、複数のソート済みのリストを一つのソート済みのリストにまとめる操作です。次の図を見てください。
┌─ [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 をセットする
データがなくなるまで繰り返す
図 : リストのマージ
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
それでは、実際にプログラムを作ってみましょう。次のリストを見てください。
リスト : リストのマージ
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
正常に動作していますね。