リストを操作する関数は再帰定義を使うと簡単に作ることができます。実は、リスト操作と再帰定義はとても相性が良いのです。まずは、リストの長さを求める関数 my_length を作りましょう。 SML/NJ には length という同等の機能を持つ関数が用意されていますが、再帰定義を使えば簡単に作ることができます。
まず、いちばん簡単な場合を考えます。引数が空リスト nil であれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト xs の長さを求めるには、リスト xs に tl を適用したリストの長さがわかればいい、と考えるのです。それに 1 を足せば、リストの長さを求めることができます。これをプログラムすると、次のようになります。
リスト : リストの長さを求める fun my_length xs = if null xs then 0 else 1 + my_length (tl xs)
関数 null xs は引数 xs が空リストであれば真 (true) を返し、そうでなければ偽 (false) を返します。my_length は、引数 xs が空リストであれば 0 を返します。そうでなければ、引数 xs に関数 tl を適用して my_length を再帰呼び出しします。リストに tl を繰り返し適用していくと最後は空リストになります。ここで再帰呼び出しが止まって 0 を返します。そうすると、1 + my_length によって my_length の返り値に 1 を足した値を返していきます。すなわち tl した回数だけ 1 が足されるわけです。
ところで、SML/NJ では格納するデータ型によってリストの型は変化します。もしも、int list と string list で異なる関数が必要だとしたら、とても面倒なことですね。ところが SML/NJ の場合、関数をひとつ定義するだけで、int list にも string list にも対応することができます。このような関数を「多相型関数 (polymorphic function)」といいます。
多相型関数の極端な例に「恒等関数 (identity function)」があります。次の例を見てください。
- fun identity x = x; val identity = fn : 'a -> 'a - identity 10; val it = 10 : int - identity 0.5; val it = 0.5 : real - identity "foo"; val it = "foo" : string - identity [1,2,3]; val it = [1,2,3] : int list
関数 identity は引数をそのまま返す関数です。'a は「型変数」といって、任意のデータ型を表します。identity の型は 'a -> 'a なので、任意の型のデータを受け取り、同じ型を返す関数であることがわかります。したがって、identity は int, real, string, int list など、SML/NJ のデータ型であれば何でも対応することができます。
実際に my_length を定義すると次のように表示されます。
val my_length = fn : 'a list -> int
my_length の場合、任意の型 'a を格納するリストを引数に取り、int を返すことが示されています。つまり、引数が int list でも string list でも、リストであればその長さを返すことができます。このように、my_length は多相型関数として定義されます。SML/NJ の組み込み関数 null, hd, tl も多相型関数です。
それでは実際に試してみましょう。
- my_length [1,2,3,4,5,6]; val it = 6 : int - my_length ["ab", "cd", "ef"]; val it = 3 : int
正常に動作していますね。SML/NJ は型チェックを厳密に行うプログラミング言語ですが、多相型関数により柔軟なプログラミングが可能になっています。
次はリストを連結する演算子 @ と同じ動作をする関数 append を作ってみましょう。引数としてリスト xs と ys を渡して、それを連結したリストを返します。
処理手順ですが、簡単な場合から考えていきましょう。まず、リスト xs が空リストならば、リスト ys を返すだけでいいですね。次に、リスト xs に要素が 1 つしかない場合を考えてみます。これは、リスト xs に hd を適用して要素を取り出し、それをコンス演算子でリスト ys の先頭に追加すればいいでしょう。
それでは、リスト xs に要素が複数ある場合を考えてください。リスト xs を hd と tl で分解します。そして、tl xs と ys を連結したリストを求め、そのリストの先頭に hd xs を追加すれば xs と ys を連結することができます。tl xs と ys の連結は再帰呼び出しで実現することができます。これを図に示すと次のようになります。
┌────────────────────────────┐
│append( [1, 2], [3, 4] ) │
├────────────────────────────┤
│ [ 1, 2 ] │
│ ┬ ─── tl ─┐ │
│ hd ↓ │
│ │ ┌──────────────────────┐│
│ │ │append( [2], [3, 4] ) ││
│ │ ├──────────────────────┤│
│ │ │ [ 2 ] ││
│ │ │ ┬ ─ tl ─┐ ││
│ │ │ hd ↓ ││
│ │ │ │ ┌────────────────┐││
│ │ │ │ │append( [], [3, 4] ) => [3, 4] │││
│ │ │ │ └────────────────┘││
│ │ │ │ │ ││
│ │ │ └→ :: ←─┘ ││
│ │ │ [2, 3, 4] ││
│ │ └─────┼────────────────┘│
│ └──→ :: ←─┘ │
└──────┼─────────────────────┘
↓
[1, 2, 3, 4]
図：append の動作
これをプログラムすると次のようになります。
リスト : リストの結合 fun append(xs, ys) = if null xs then ys else hd xs :: append(tl xs, ys)
引数 x が空リストであればリスト y をそのまま返します。これが再帰呼び出しの停止条件になります。そうでなければ、tl x を append に渡して再帰呼び出しします。そして、その返り値と hd x をコンス演算子で接続します。これでリストを連結することができます。
実際に append を定義すると、次のように表示されます。
val append = fn : 'a list * 'a list -> 'a list
append も多相型関数になります。簡単な実行例を示します。
- append([1, 2, 3], [4, 5, 6]); val it = [1,2,3,4,5,6] : int list - append(["ab", "cd"], ["ef", "gh"]); val it = ["ab","cd","ef","gh"] : string list
今度はリストの要素を反転する関数 reverse を作ってみましょう。SML/NJ には rev という同等の機能を持つ関数が用意されていますが、再帰定義で簡単に作ることができます。reverse は引数のリスト xs を hd と tl で分解し、tl xs を反転させてから hd xs を最後尾に追加することで実現できます。次の図を見てください。
[1, 2, 3] [3, 2] @ [1] => [3, 2, 1]
↓ ↑
[2, 3] [3] @ [2] => [3, 2]
↓ ↑
[3] nil @ [3] => [3]
↓ ↑
nil ──┘
図 : reverse の動作
これをプログラムすると、次のようになります。
リスト : リストの反転 fun reverse xs = if null xs then nil else reverse (tl xs) @ [hd xs]
引数 xs が空リストの場合は nil を返します。そうでなければ、reverse を再帰呼び出しして tl xs を反転し、演算子 @ で反転したリストの最後尾に先頭の要素を追加します。
実際に reverse を定義すると、次のように表示されます。
val reverse = fn : 'a list -> 'a list
reverse も多相型関数になります。簡単な実行例を示します。
- reverse [1, 2, 3]; val it = [3,2,1] : int list - reverse [1, 2, 3, 4, 5, 6, 7, 8, 9]; val it = [9,8,7,6,5,4,3,2,1] : int list - reverse ["ab", "cd", "ef"]; val it = ["ef","cd","ab"] : string list
次はリストからデータを探索する関数 member を作ってみましょう。関数の名前と動作は Common Lisp から拝借しました。member はリストの中にデータがなければ空リスト (nil) を返します。データを見つけた場合は、そのリストの残りを返します。つまり、返り値のリストの先頭要素が見つけたデータになります。
プログラムは次のようになります。
リスト : リストの探索 fun member(x, ys) = if null ys then nil else if x = hd ys then ys else member(x, tl ys)
関数 member はリスト ys の中から x を探します。これは member を再帰呼び出ししてリストを分解し、リストの先頭要素をチェックしていくことで実現できます。ys が空リストの場合は x を見つけることができなかったので nil を返します。次に、リスト ys の先頭の要素 hd ys が x と等しいかチェックします。そうであれば、リスト ys をそのまま返します。この 2 つが再帰の停止条件になります。そうでなければ、member を再帰呼び出しして次の要素を調べます。
実際に member を定義すると、次のように表示されます。
val member = fn : ''a * ''a list -> ''a list
''a は ' が 2 個ついていますが、これを「等値型」の型変数といいます。等値型とは、等値演算子 (=, <>) で比較できるデータ型のことです。int, real, string, bool などの基本的なデータ型は等値型です。また、要素が等値型の組やリストも等値型になります。次の例を見てください。
- (1,2) = (1,2); val it = true : bool - (1,2) = (2,1); val it = false : bool - [1,2,3] = [1,2,3]; val it = true : bool - [1,2,3] = [3,2,1]; val it = false : bool
member は多相型関数ですが、データの比較で演算子 = を使っているため、等値型のデータに制限されているのです。
それでは、簡単な実行例を示します。
- member(3, [1,2,3,4,5]);
val it = [3,4,5] : int list
- member(5, [1,2,3,4,5]);
val it = [5] : int list
- member(0, [1,2,3,4,5]);
val it = [] : int list
- member("ab", ["ab", "cd", "ef"]);
val it = ["ab","cd","ef"] : string list
- member("ac", ["ab", "cd", "ef"]);
val it = [] : string list
関数を定義する場合、引数に「パターン (pattern)」を使うことができます。SML/NJ のパターン機能は、論理型言語 Prolog の「パターンマッチング (pattern matching)」とよく似ています。たとえば、パターンを使って階乗を求める関数 fact を定義すると次のようになります。
リスト : 階乗 fun fact n = if n = 0 then 1 else n * fact(n - 1) (* パターンを利用 *) fun fact 0 = 1 | fact n = n * fact(n - 1)
(* ... *) はコメントを表します。SML/NJ の場合、コメントは入れ子になってもかまいません。パターンを使って関数を定義する場合、縦線 | で複数の関数定義をつなげます。このとき、当然ですが関数は同じ名前にしてください。SML/NJ は引数とパターンがマッチングする関数を選択して実行します。
パターンが定数の場合、同じ値の引数とマッチングします。最初の定義はパターンが 0 なので、引数が 0 の場合にマッチングします。これは if n = 0 then 1 と同じ処理です。パターンが変数の場合、どんな値とでもマッチングします。したがって、n が 0 以外の場合は 2 番目の定義と一致します。ここで再帰呼び出しが行われます。このように、if を使わなくてもパターンでプログラムを作ることができます。
パターンを使うときは、関数を定義する順番に気をつけてください。fact の場合、最初に fact n を定義すると、引数が 0 の場合でもマッチングするので、fact 0 が選択されなくなります。引数を特定するパターンから定義するように注意してください。
パターンは定数や変数だけではなく、組やリストにも適用することができます。また、関数の引数だけではなく、val で変数を宣言するときにもパターンを使うことができます。次の例を見てください。
- val (a, b) = (1, 2); val a = 1 : int val b = 2 : int - val ((c, d), e) = ((1, 2), 3); val c = 1 : int val d = 2 : int val e = 3 : int
このように、パターンを使って組の要素を取り出すことができます。型が違うとマッチングに失敗してエラーになります。ご注意ください。
リストもパターンとマッチングすることができます。リストのパターンはコンス演算子 :: を使って表します。たとえば、パターンを使って関数 append を定義すると次のようになります。
リスト : リストの連結 fun append(nil, ys) = ys | append(x::xs, ys) = x :: append(xs, ys)
最初の定義は、第 1 引数が nil とマッチングします。次の定義の x::xs がパターンを表します。このパターンはリストとマッチングして、先頭の要素が x に、先頭要素を取り除いた残りのリストが xs に束縛されます。このように、関数 hd や tl を使わなくてもリストを分解することができます。
リストを表すパターンは x::xs だけではありません。よく使われるパターンを次に示します。
(1) [x] 要素が 1 つのリストとマッチング (2) [x, y] 要素が 2 つのリストとマッチング (3) x::xs 要素が 1 つ以上あるリストとマッチング (4) x1::x2::xs 要素が 2 つ以上あるリストとマッチング (5) x1::x1::xs エラー
(5) のように、パターンの中に同名の変数を使うことはできません。この場合、x1::x2::xs とマッチングさせてから if で x1 と x2 が等しいかチェックすることになります。また、もっと複雑なリストもパターンで表すことができます。
(1) (x, y)::xs 要素が組のリストとマッチング
ex) [(1, 2), (3, 4), (5, 6)] => x = 1, y = 2, xs = [(3, 4), (5, 6)]
(2) (x::xs)::ys 要素がリストのリスト ('a list list) とマッチング
ex) [[1, 2, 3], [4, 5], [6]] => x = 1, xs = [2, 3], ys = [[4, 5], [6]]
このように、パターンはとても強力な機能です。SML/NJ は型チェックを厳密に行う関数型言語ですが、型推論、多相型関数、パターンなどの機能により、とても柔軟にプログラミングすることができます。
それでは例題としてリストをソート (sort) するプログラムを作ってみましょう。ソートは、ある規則に従ってデータを順番に並べることです。たとえば、データが整数であれば、大きい順かもしくは小さい順に並べます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でも「クイックソート (quick sort)」は高速のアルゴリズムとして有名です。もちろん、SML/NJ でもクイックソートをプログラムすることができます。要素が整数のリストをクイックソートしてみることにしましょう。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
[5, 3, 7, 6, 9, 8, 1, 2, 4]
5 を枢軸に分割
[3, 1, 2, 4] 5 [7, 6, 9, 8]
3を枢軸に分割 7を枢軸に分割
[1, 2] 3 [4] | 5 | [6] 7 [9, 8]
・・・分割を繰り返していく・・・
図 : クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを結合していけばいいわけです。プログラムは次のようになります。
リスト : クイックソート
fun quick_sort nil = nil
| quick_sort (x::xs) =
let
val (m, n) = partition(x, xs)
in
quick_sort m @ (x :: quick_sort n)
end
最初の定義が空リストの場合で、再帰呼び出しの停止条件になります。次の定義でリストを分割してソートを行います。パターン x::xs でリストを分解し、リストの先頭要素 x を枢軸とします。リストの分割は関数 partition で行います。partition は x を基準にリストを 2 つに分割し、それらのリストを組 (a, b) で返します。リスト a が枢軸よりも小さな要素を集めたもので、リスト b が枢軸以上の要素を集めたものです。
quick_sort では let で局所変数 m と n を定義し、partition を呼び出して返り値をパターンで受け取ります。そして、quick_sort を再帰呼び出しして、リスト m, n をソートします。あとは、その結果を枢軸 x を挟んで結合すればいいわけです。
次はリストを分割する関数 partition を説明します。
リスト : リストの分割
fun partition(_, nil) = (nil, nil)
| partition(n, x::xs) =
let
val (a, b) = partition(n, xs)
in
if x < n then (x::a, b) else (a, x::b)
end
最初の定義が空リストの場合です。これが再帰呼び出しの停止条件になります。第 1 引数の アンダーライン ( _ ) は「匿名変数 (anonymous variable)」です。匿名変数はどの値ともマッチングするワイルドカードとして機能します。ただし、マッチングした値を参照することはできません。値を必要としない引数は匿名変数を使うと便利です。空リストの場合は 組 (nil, nil) を返します。
次の定義でリストを分割します。引数のリストをパターン x::xs で分解し、partition を再帰呼び出ししてリスト xs を 2 つに分割します。返り値は局所変数 (a, b) で受け取ります。あとは、枢軸 n と要素 x を比較して、x が n よりも小さければ x をリスト a に追加して返します。そうでなければ、x をリスト b に追加して返します。これで枢軸 n を基準にしてリストを 2 分割することができます。
それでは、簡単な実行例を示しましょう。
val quick_sort = fn : int list -> int list - quick_sort [5,3,7,6,9,8,1,2,4]; val it = [1,2,3,4,5,6,7,8,9] : int list
正常に動作していますね。ところで、今回のプログラムは要素の比較に演算子 < を使ったため、リストの型は int list になりました。実をいうと、リストの要素を比較する関数を引数として渡すように改良すると、quick_sort を多相型関数として定義することができます。これは「高階関数」のところで詳しく説明します。
次に示すリスト操作関数をパターンマッチングを使って定義してください。
- fun take(nil, _) = nil
= | take(_, 0) = nil
= | take(x::xs, n) = x :: take(xs, n - 1);
val take = fn : 'a list * int -> 'a list
- take([1,2,3,4,5], 3);
val it = [1,2,3] : int list
- take([1,2,3,4,5], 0);
val it = [] : int list
- take([1,2,3,4,5], 5);
val it = [1,2,3,4,5] : int list
- fun drop(nil, _) = nil
= | drop(xs, 0) = xs
= | drop(_::xs, n) = drop(xs, n - 1);
val drop = fn : 'a list * int -> 'a list
- drop([1,2,3,4,5], 0);
val it = [1,2,3,4,5] : int list
- drop([1,2,3,4,5], 3);
val it = [4,5] : int list
- drop([1,2,3,4,5], 5);
val it = [] : int list
- fun zip(nil, _) = nil
= | zip(_, nil) = nil
= | zip(x::xs, y::ys) = (x, y) :: zip(xs, ys);
val zip = fn : 'a list * 'b list -> ('a * 'b) list
- zip([1,2,3],[4,5,6]);
val it = [(1,4),(2,5),(3,6)] : (int * int) list
- zip([1,2,3],[4,5]);
val it = [(1,4),(2,5)] : (int * int) list
- zip([1,2],[4,5,6]);
val it = [(1,4),(2,5)] : (int * int) list
- fun unzip nil = (nil, nil)
= | unzip ((x, y)::zs) = let val (a, b) = unzip zs in (x::a, y::b) end;
val unzip = fn : ('a * 'b) list -> 'a list * 'b list
- unzip [(1,2),(3,4),(5,6)];
val it = ([1,3,5],[2,4,6]) : int list * int list
- fun make_list(_, 0) = nil
= | make_list(x, n) = x :: make_list(x, n - 1);
val make_list = fn : 'a * int -> 'a list
- make_list(1, 10);
val it = [1,1,1,1,1,1,1,1,1,1] : int list
- make_list("foo", 3);
val it = ["foo","foo","foo"] : string list