変数の有効範囲を表す用語に「スコープ (scope) 」があります。この用語を使うと、厳密ではありませんが、変数の有効範囲は「レキシカルスコープ」と「ダイナミックスコープ」の 2 つに分けることができます。伝統的な Lisp はダイナミックスコープですが、近代的なプログラミング言語、たとえば Common Lisp, Scheme, SML/NJ はレキシカルスコープを採用しています。
それでは、レキシカルスコープについて詳しく見てみましょう。変数 x を表示する関数 foo を定義します。
- val x = "global\n"; val x = "global\n" : string - fun foo() = print x; val foo = fn : unit -> unit - foo(); global val it = () : unit
関数 foo には局所変数 x を定義していないので、foo を実行した場合は大域変数の値を参照します。その結果 global が表示されます。それでは、foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 には let で局所変数 x を定義します。この場合、foo はどちらの値を表示するのでしょうか。実際に試してみましょう。
- fun foo1() = let val x = "local\n" in foo() end; val foo1 = fn : unit -> unit - foo1(); global val it = () : unit
大域変数の値 global を表示しました。このように、foo1 で定義した局所変数 x は、foo から参照することはできません。次の図を見てください。
┌────── SML/NJ system ──────┐
│ │
│ 大域変数 x ←────┐ │
│ │ │
│ ┌→┌─ 関数 foo ──────┐ │ │
│ │ │ ┌──────┼─┘ │
│ │ │ print x │ │
│ │ │ │ │
│ │ └────────────┘ │
│ │ ┌─ 関数 foo1 ─────┐ │
│ │ │ │ │
│ │ │ ┌─let : x ───┐ │ │
│ │ │ │ │ │ │
│ └─┼─┼─ foo() │ │ │
│ │ └────────┘ │ │
│ └────────────┘ │
│ │
└────────────────────┘
図 : レキシカルスコープ
上図では変数の有効範囲を枠で表しています。foo1 の let で定義した局所変数 x は、let の枠の中でのみ有効です。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。順番に外側の枠を調べていくと、最後には関数定義の枠に行き着きます。ここで変数（引数）が見つからない場合は大域変数を調べます。
関数 foo は関数定義の枠しかありません。そこに変数 x が定義されていないので、大域変数を調べることになるのです。このように、関数 foo から foo1 の枠と let の枠を超えて変数 x にアクセスすることはできないのです。これを「レキシカルスコープ (lexical scope) 」といいます。レキシカルには文脈上いう意味があり、変数が定義されている構造の範囲内 (枠内) でないと、その変数にアクセスすることはできません。
ところが伝統的な Lisp の場合、foo1 で定義した変数 x は呼び出された関数 foo からアクセスすることができます。これを「ダイナミックスコープ (dynamic scope) 」といいます。foo1 で定義された変数 x は、foo1 の実行が終了するまで存在し、foo1 から呼ばれた関数ならば、どこからでも参照することができます。もしも、foo1 をダイナミックスコープの処理系、たとえば Emacs Lisp で実行するならば、foo で表示される x の値は local になります。
それでは、匿名関数や局所的な関数の場合はどうでしょうか。次の例を見てください。
リスト : リストの要素を n 倍する fun mapcar( _, nil ) = nil | mapcar( f, x::xs ) = f( x ) :: mapcar( f, xs ) fun times_element( n, l ) = mapcar( fn(x) => x * n, l )
匿名関数の引数は x だけですから、変数 n は大域変数を参照するように思われるかもしれません。ところが、変数 n は関数 times_element の引数 n を参照するのです。これを図に示すと、次のようになります。
┌────── SML/NJ system ─────┐
│ │
│ ┌─ times_element : n, l ─┐ │
│ │ ↑ │ │
│ │ └─┐ │ │
│ │ ┌── fn : x ──┐│ │ │
│ │ │ ↑ ││ │ │
│ │ │ ┌──┘ ││ │ │
│ │ │ x * n ││ │ │
│ │ │ └───┼┘ │ │
│ │ └────────┘ │ │
│ └─────────────┘ │
│ │
└───────────────────┘
図 : 匿名関数内の変数
ポイントは、匿名関数が times_element 内で定義されているところです。変数 n は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。匿名関数はその範囲内に定義されているため、変数 n にアクセスすることができるのです。つまり、関数内で定義された匿名関数は、そのとき有効な局所変数にアクセスすることができるのです。
これは let で定義された局所的な関数も同じです。times_element は次のように書き換えることができます。
リスト : リストの要素を n 倍する
fun times_element( n, l ) =
let
fun timesN( x ) = x * n
in
mapcar( timesN, l )
end
関数 timesN は times_element 内で定義されているので、timesN から times_element の引数 n を参照することができます。
簡単な例題として、クイックソートを高階関数に改良してみましょう。データを比較する関数を渡すことで、クイックソートを多相型関数にすることができます。次のリストを見てください。
リスト : クイックソート
fun quicksort( _, nil ) = nil
| quicksort( f, x::xs ) =
let
(* リストの分割 *)
fun partition( _, nil, a, b ) = (a, b)
| partition( z, y::ys, a, b ) =
if f(y, z) then partition( z, ys, y::a, b )
else partition( z, ys, a, y::b )
val (m, n) = partition( x, xs, nil, nil )
in
quicksort( f, m ) @ (x :: quicksort( f, n ))
end
quicksort の第 1 引数 f がデータを比較する関数、第 2 引数がリストです。リストを分割する関数 partition は quicksort 内で定義しているので、quicksort の引数 f を参照することができます。わざわざ関数 f を partition に渡す必要はありません。なお、partition は末尾再帰でプログラムしています。ご注意ください。
それでは、実行例を示します。
val quicksort = fn : ('a * 'a -> bool) * 'a list -> 'a list
- quicksort( op <, [5,9,1,8,2,7,3,6,4] );
val it = [1,2,3,4,5,6,7,8,9] : int list
- quicksort( op >, [5,9,1,8,2,7,3,6,4] );
val it = [9,8,7,6,5,4,3,2,1] : int list
- quicksort( op <, ["c", "a", "d", "e", "b"] );
val it = ["a","b","c","d","e"] : string list
関数型をみると quicksort は多相型関数として定義されていることがわかります。比較関数を渡すことで、データを昇順でも降順でもソートすることができます。
Lisp などの関数型言語では、関数を生成する関数を簡単に作ることができます。このとき使われる機能が「クロージャ (closure) 」です。クロージャは評価する関数と参照可能な局所変数をまとめたものです。クロージャは関数のように実行することができますが、クロージャを生成するときに参照可能な局所変数を保持するところが異なります。参照可能な局所変数の集合を「環境」と呼ぶことがあります。
SML/NJ でクロージャを生成するには「匿名関数」を使うか、局所的な関数を定義して、その関数を返します。たとえば、「引数を n 倍する関数」を生成する関数は、匿名関数を使うと次のようになります。
- fun foo( n ) = fn( x ) => n * x; val foo = fn : int -> int -> int - val foo10 = foo( 10 ); val foo10 = fn : int -> int - foo10( 100 ); val it = 1000 : int - val foo5 = foo( 5 ); val foo5 = fn : int -> int - foo5( 11 ); val it = 55 : int
関数 foo は引数を n 倍する関数を生成します。関数 foo の型 int -> int -> int は int -> (int -> int) を意味し、引数 int を受け取り int -> int という関数を返すことを表しています。-> は四則演算とは違って右結合になります。
変数 foo10 に foo( 10 ) の返り値をセットします。すると、foo10 は引数を 10 倍する関数として使うことができます。同様に、変数 foo5 に foo( 5 ) の返り値をセットすると、foo5 は引数を 5 倍する関数になります。
匿名関数を生成するとき、評価する関数のほかに、そのとき参照可能な局所変数、つまり「環境」もいっしょに保存されます。この場合、参照可能な局所変数は foo の引数 n です。そして、クロージャを実行するときは、保存されている局所変数を参照することができるのです。
foo( 10 ) を実行して無名関数を生成するとき、定義されている局所変数は n で、その値は 10 ですね。この値がクロージャに保存されているので、foo10 の関数は引数を 10 倍した結果を返します。foo( 5 ) を評価すると n の値は 5 で、それがクロージャに保存されているので、foo5 の関数は引数を 100 倍した結果を返すのです。
また、let で局所的な関数を定義して、その関数を返すとクロージャを生成することができます。let を使った例を示します。
- fun foo( n ) = let fun bar(x) = n * x in bar end; val foo = fn : int -> int -> int - val foo100 = foo( 100 ); val foo100 = fn : int -> int - foo100( 11 ); val it = 1100 : int
let で関数 bar を定義して、bar を返します。すると、foo は「引数を n 倍する関数」を生成する関数になります。
クロージャを理解する場合、環境を連想リストで考えるとわかりやすいと思います。通常、関数を呼び出す場合、関数を評価するための環境は空リストです。最初に、引数がこの環境に追加されます。let で定義される局所変数もこの環境に追加されます。もしも、環境に該当する変数が存在しない場合は大域変数を参照します。
たとえば、foo( 5 ) と呼び出すと環境は次のようになります。
foo( 5 ) ==> 環境 : [(n, 5)]
連想リストの n が変数名で、その値が 5 です。クロージャを生成するとき、この連想リストを保持すると考えてください。そして、クロージャを評価するときは、保存していた環境を使います。したがって、foo5( 11 ) を評価すると、環境 [(n, 5)] に引数 x の値が追加され、[(x, 11), (n, 5)] になります。この環境で式 n * x を評価するので、5 * 11 = 55 を返すわけです。
関数の評価が終了すると、環境に追加された変数は削除されます。foo5( 11 ) の評価で追加された変数は x なので、(x, 11) が削除され [(n, 5)] になります。このように、クロージャに保存された環境は変化しません。
ただし、Lisp や Scheme のように、変数の値を書き換えることができる処理系では、クロージャに保存された変数の値を変更することが可能です。興味のある方は Common Lisp 入門：クロージャ を読んでみてください。
クロージャは Lisp でも使える方法です。ところが、SML/NJ にはもっと簡単な方法が用意されています。それは関数を「カリー化形式 (Curried form) 」で定義することです。これを「カリー化関数」といいます。次の例を見てください。
- fun bar x y = x * y; val bar = fn : int -> int -> int - bar 10 11; val it = 110 : int - val bar10 = bar 10; val bar10 = fn : int -> int - bar10 1000; val it = 10000 : int - val bar5 = bar 5; val bar5 = fn : int -> int - bar5 111; val it = 555 : int
関数をカリー化する場合、引数をカッコで囲わず、カンマでも区切りません。関数 bar の型を見ると int -> int -> int になっていますね。これで引数を一つだけ与えれば、関数を返すことになります。もちろん、引数を 2 つ与えれば、それらを乗算した結果を返します。これは、最初の引数を受け取って関数を生成し、その関数を 2 番目の引数に適用する、という動作になります。SML/NJ の場合、カリー化関数はよく使われる方法です。
関数のカリー化は高階関数でも行うことができます。たとえば、mapcar をカリー化すると次のようになります。
リスト : mapcar のカリー化 fun mapcar_c _ nil = nil | mapcar_c f (x::xs) = f x :: mapcar_c f xs
関数 mapcar_c は mapcar をカリー化したものです。カリー化関数の引数は空白で区切るだけなので、パターン x::xs はカッコで囲む必要があります。実際に mapcar_c を定義すると次のようになります。
val mapcar_c = fn : ('a -> 'b) -> 'a list -> 'b list
カリー化により mapcar の関数型は ('a -> 'b) * 'a list の部分が ('a -> 'b) -> 'a list に変わっています。つまり、関数型 'a -> 'b を引数に受け取り、'a list -> 'b list という関数を返すことが示されています。次の実行例を見てください。
- val foo = mapcar_c (fn(x) => x * x); val foo = fn : int list -> int list - foo [1,2,3,4,5]; val it = [1,4,9,16,25] : int list - mapcar_c (fn(x) => x * x) [1,2,3,4,5]; val it = [1,4,9,16,25] : int list
mapcar_c に値を 2 乗する関数を渡すと、リストの要素を 2 乗する関数を生成することができます。この関数を変数 foo に束縛し、リストに foo を適用すると要素が 2 乗されたリストが返されます。もちろん、mapcar_c に関数とリストを渡して評価することもできます。
SML/NJ で用意されいる高階関数のほとんどがカリー化されています。ここで、代表的な高階関数を紹介しましょう。
val map : ('a -> 'b) -> 'a list -> 'b list
val app : ('a -> unit) -> 'a list -> unit
map は mapcar_c と同じくマッピングを行う関数です。app は副作用を伴う関数を受け取り、それをリストの要素に適用します。リストの要素を出力するときに便利です。簡単な実行例を示します。
- val squareList = map (fn(x) => x*x); val squareList = fn : int list -> int list - squareList [1,2,3,4,5]; val it = [1,4,9,16,25] : int list - val printIntlist = app (fn(x) => print(Int.toString(x)^"\n")); val printIntlist = fn : int list -> unit - printIntlist [1,2,3,4,5]; 1 2 3 4 5 val it = () : unit
map に fn(x) => x * x を渡すと、リストの要素を 2 乗する関数を作成することができます。map の返り値を変数 squareList に束縛すると、squareList はリストの要素を 2 乗する関数として使うことができます。同様に、app に整数を表示する関数を渡して返り値を printIntlist に束縛すると、printIntlist は int list を表示する関数になります。
val foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
foldr と foldl は 高階関数 で説明した reduce と同じ働きをする関数です。foldr と foldl の動作は次のようになります。
foldr f g [a1, a2, a3, ..., an-1, an] => f( a1, f( a2, f( a3, ..., f( an, g ) ... ))) foldl f g [a1, a2, a3, ..., an-1, an] => f( an, f( an-1, f( an-2, ..., f( a1, g ) ... )))
foldl の動作は 高階関数 で説明した reduce の動作と少し異なります。SML/NJ の場合、foldl f g list は foldr f g (rev list) と同じになります。rev はリストを反転する SML/NJ の関数です。簡単な例を示します。
- fun count_if f l = foldr (fn(x, y) => if f x then y + 1 else y) 0 l;
val count_if = fn : ('a -> bool) -> 'a list -> int
- count_if (fn(x) => x >= 10) [1,11,2,12,3,13,4];
val it = 3 : int
- fun remove_if f l = foldr (fn(x, y) => if f x then y else x::y) nil l;
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
foldr を使って関数 count_if を定義します。count_if は述語 f が真となる要素の個数を数える関数です。匿名関数 fn(x, y) の引数 x がリストの要素、y が条件を満たした要素の個数になります。f x が真ならば y + 1 を返し、そうでなければ y を返します。これで条件を満たす要素をカウントすることができます。
次は関数 remove_if を定義します。remove_if は述語 f が真となる要素を削除する関数です。匿名関数 fn(x, y) で、f x が真であれば y をそのまま返し、そうでなければ x を y のリストに追加します。これで条件を満たす要素を削除することができます。
SML/NJ の場合、リストを操作する関数はストラクチャ List に定義されています。その中から filter, find, exists, all を説明します。
val filter : ('a -> bool) -> 'a list -> 'a list
val find : ('a -> bool) -> 'a list -> 'a option
val exists : ('a -> bool) -> 'a list -> bool
val all : ('a -> bool) -> 'a list -> bool
filter は 高階関数 で説明した「フィルター」と同じ働きをする関数です。filter f l は述語 f が真となる要素をリストに格納して返す関数で、remove_if と逆の働きをします。find f l は述語 f が真となる要素を探す関数です。exists f l は述語 f を満たす要素が一つでもあれば真を返し、そうでない場合は偽を返します。逆に、all f l は全ての要素が述語 f を満たせば真を返し、述語 f を満たさない要素が一つでもあれば偽を返します。簡単な使用例を示します。
- List.filter (fn(x) => x >= 10 andalso x < 20) [1,5,10,15,20,25]; val it = [10,15] : int list - List.find (fn(x) => x mod 2 = 0) [1,5,10,15,20]; val it = SOME 10 : int option - List.exists (fn(x) => x mod 2 = 0) [1,5,10,15]; val it = true : bool - List.all (fn(x) => x mod 2 = 0) [2,4,6,8,10]; val it = true : bool
関数 f(x) と g(x) を合成して新しい関数 h(x) を作ることを考えてみましょう。関数 h(x) を次のように定義します。
h(x) = g( f(x) )
関数 f(x) の返り値が関数 g(x) の引数になるので、関数 g(x) が受け付ける値でなければいけません。そうでないと関数を合成することはできません。この条件を SML/NJ の型で表すと、次のようになります。
g : 'a -> 'b, f : 'c -> 'a, h : 'c -> 'b
関数 f の返り値が型 'a ならば、関数 g の引数も型は 'a でなければいけません。SML/NJ の場合、関数を合成する演算子 o が用意されています。演算子 o の型を示します。
- op o;
val it = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b
演算子 o は 2 つの関数を受け取り、それらを合成した関数を返します。'a -> 'b が関数 g で、'c -> 'a が関数 f になります。そして、関数 f と g を合成した新しい関数 'c -> 'b を返します。簡単な例を示しましょう。
- fun foo x = 2 * x + 1; val foo = fn : int -> int - fun bar y = y * y + 3 *y; val bar = fn : int -> int - bar( foo( 4 ) ); val it = 108 : int - val baz = bar o foo; val baz = fn : int -> int - baz 4; val it = 108 : int - (bar o foo) 4; val it = 108 : int
関数 foo と bar を定義します。foo と bar の合成は bar( foo( x ) ) と表すことができます。実際に 4 を計算すると 108 になります。これらの関数は bar o foo で合成することができます。その値を変数 baz に束縛すると、baz を合成関数として使うことができます。また、最後の例のように、合成関数 (bar o foo) をそのまま使うこともできます。
もちろん、高階関数も合成することができます。リストの要素を 2 乗して、10 以上の値を取り出す関数は、filter と map を合成すると簡単に作ることができます。
- val foo = (List.filter (fn(x) => x >= 10)) o (map (fn(x) => x * x)); val foo = fn : int list -> int list - foo [1,2,3,4,5]; val it = [16,25] : int list
このように、SML/NJ は関数を柔軟に操作することができます。
今回は組み合わせの数を求めるプログラムを作ってみましょう。ここでは組み合わせの数 nＣr を (n, r) と表記します。(n, r) を求めるには、次の公式を使えば簡単です。
(n, r) = n * (n - 1) * (n - 2) * ... * (n - r + 1) / (1 * 2 * 3 * ... * r)
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。SML/NJ は Common Lisp のような多倍長整数をサポートしていないので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。
(n, 0) = (n, n) = 1 (n, r) = (n, r - 1) * (n - r + 1) / r
この式は (n, r) と (n, r-1) の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。
リスト : 組み合わせの数を求める
fun ncr( n, r ) =
if n = r orelse r = 0 then 1
else ncr( n, r - 1 ) * (n - r + 1) div r
とても簡単ですね。ところで、SML/NJ の整数 (int) は 31 bit (~1073741824 から 1073741823 まで) なので、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。
- ncr(16, 8); val it = 12870 : int - ncr( 18, 9 ); val it = 48620 : int - ncr( 20, 10 ); val it = 184756 : int - ncr( 22, 11 ); val it = 705432 : int - ncr( 24, 12 ); val it = 2704156 : int - ncr( 26, 13 ); val it = 10400600 : int - ncr( 28, 14 ); val it = 40116600 : int - ncr( 30, 15 ); uncaught exception overflow
SML/NJ の場合、桁あふれが発生すると例外 overflow が送出されます。桁あふれを起こさないようにするには、モジュール IntInf を使います。SML/NJ はコロン ( : ) を使ってデータ型を指定することができます。
リスト : 組み合わせの数を求める (2)
fun ncr1( n, r ) =
if n = r orelse r = 0 then 1 : IntInf.int
else ncr1( n, r - 1 ) * (n - r + 1) div r
(* 関数の引数で型指定してもよい *)
fun ncr1( n : IntInf.int, r ) =
if n = r orelse r = 0 then 1
else ncr1( n, r - 1 ) * (n - r + 1) div r
val ncr1 = fn : IntInf.int * IntInf.int -> IntInf.int
返り値の整数 1 に : IntInf.int を指定することで、計算を多倍長整数で行うことができます。また、関数の引数で型指定を行ってもかまいません。それでは実行してみましょう。
- ncr1(30, 15); val it = 155117520 : IntInf.int - ncr1(50, 25); val it = 126410606437752 : IntInf.int - ncr1(100, 50); val it = 100891344545564193334812497256 : IntInf.int
このように、IntInf モジュールを使って多倍長整数で計算を行うことができます。
それでは、関数 ncr を使って「パスカルの三角形」を作ってみましょう。次の図を見てください。
１ 0Ｃ0
／ ＼ ／ ＼
１ １ 1Ｃ0 1Ｃ1
／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ２ １ 2Ｃ0 2Ｃ1 2Ｃ2
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ３ ３ １ 3Ｃ0 3Ｃ1 3Ｃ2 3Ｃ3
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ４ ６ ４ １ 4Ｃ0 4Ｃ1 4Ｃ2 4Ｃ3 4Ｃ4
図 : パスカルの三角形
パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは (a + b)n を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 nＣr に対応しています。
きれいな三角形にはなりませんが、パスカルの三角形を表示するプログラムを示します。
リスト : パスカルの三角形
fun print_int( n ) = print( Int.toString( n ) ^ " " )
fun pascal( x ) =
let
fun pas( n, r ) =
if x < n then ()
else if n < r then (print("\n"); pas( n + 1, 0 ))
else (print_int( ncr( n, r ) ); pas( n, r + 1 ))
in
pas( 0, 0 )
end
手続き型言語では「二重ループ」で簡単にプログラムできるのですが、SML/NJ の while ループはまだ説明していないので、再帰定義でプログラムしました。pas( n, r ) で x < n の場合が再帰呼び出しの停止条件です。n < r の場合は三角形の 1 行を表示したので、print("\n") で改行してから pas を再帰呼び出しして次の行を表示します。そうでない場合は、ncr( n, r ) の値を表示して pas を再帰呼び出しします。
それでは実行結果を示します。
- 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
ところで、関数 ncr を使わないでパスカルの三角形を出力するプログラムを作ってみるのも面白いと思います。興味のある方は挑戦してみてください。
今度は「順列 (permutation) 」を生成するプログラムを作ってみましょう。異なる n 個の順列の総数は、n の階乗 (n!) だけあります。たとえば、3 つの整数 1, 2, 3 の順列は次に示すように 6 通りあります。
1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1
順列を生成するプログラムは再帰定義で簡単に作ることができます。[1, 2, 3] の順列を生成する場合、最初に 1 で始まる順列を生成します。これは 1 を取り除いた数字 [2, 3] の順列を生成することで実現できます。次は 2 で始まる順列を生成します。同様に、2 を取り除いた数字 [1, 3] の順列を生成すればいいわけです。[2, 3] や [1, 3] の順列を生成する場合も同じように考えることができます。
プログラムは次のようになります。
リスト : 順列の生成 (1)
(* 順列の表示 *)
fun print_intlist( nil ) = print( "\n" )
| print_intlist( x::xs ) =
( print( Int.toString(x) ^ " " ); print_intlist( xs ) )
(* 数字の削除 *)
fun remove( _, nil ) = nil
| remove( n, x::xs ) =
if x = n then xs else x::remove( n, xs )
(* 順列の生成 *)
fun perm( nil, y ) = print_intlist( rev y )
| perm( nums, y ) =
app ( fn( x ) => perm( remove( x, nums ), x::y ) ) nums
関数 perm の第 1 引数が数字のリストです。perm は第 1 引数の順列を生成します。第 2 引数が選んだ数字を格納するリストです。これが生成した順列になります。最初の定義が数字を全て選んだ場合です。順列がひとつ完成したので print_intlist で rev y を表示します。選んだ数字はリストの先頭に追加していくので、逆順になることに注意してください。
次の定義で数字を一つ選んで perm を再帰呼び出しします。数字の選択はリストの先頭から順番に行えばいいので、高階関数 app を使っています。匿名関数でリストの要素 x を受け取り、この中で prem を再帰呼び出しします。perm の第 1 引数は nums から x を削除したリスト、第 2 引数は選択した数字のリスト y に x を追加したものです。これで数字 x を選択したことになります。x の削除は関数 remove で行います。
関数 remove はリスト y から x を探し、最初に見つけた x を削除します。今回の処理は要素を一つだけ削除すればよいので、x を見つけたら残りのリスト xs をそのまま返します。filter を使う場合は、次のようになります。
fun remove( n, l ) = List.filter ( fn(x) => x <> n ) l
filter を使うとリスト l の要素を最後まで調べるので、実行速度は少しだけ遅くなるかもしれません。まあ、要素数が少ない場合は、ほとんど差はないでしょう。
print_intlist は再帰定義でプログラムしましたが、app を使ってもよいでしょう。その場合は、次のようになります。
fun print_intlist( l ) =
( app ( fn( x ) => print( Int.toString( x ) ^ " " ) ) l; print ("\n") )
それでは、実際に試してみましょう。
- perm( [1,2,3], nil ); 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 val it = () : unit
正常に動作していますね。生成した順列をリストに格納して返す場合は、foldr を使うと簡単です。プログラムは次のようになります。
リスト : 順列の生成 (2)
fun perm_list( x ) =
let
fun perm_sub( nil, y, z ) = (rev y)::z
| perm_sub( nums, y, z ) =
foldr ( fn(a, b) => perm_sub( remove( a, nums ), a::y, b ) ) z nums
in
perm_sub( x, nil, nil )
end
関数 perm_sub は perm を改造したもので、生成した順列を第 3 引数のリストに格納します。perm_sub は順列を格納したリスト (第 3 引数) をそのまま返します。perm_sub を呼び出す場合、この返り値を第 3 引数に渡すことで、生成した順列を格納していくことができます。
foldr の初期値を第 3 引数の z にすることで、匿名関数 fn(a, b) の第 2 引数 b に順列を格納するリストを渡します。あとは perm_sub を再帰呼び出しすると、その返り値は次に匿名関数 fn(a, b) を呼び出すときの引数 b に渡されるので、順列を格納したリストを perm_sub に渡していくことができます。
それでは実行結果を示します。
val perm_list = fn : ''a list -> ''a list list - perm_list([1,2,3]); val it = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] : int list list
正常に動作していますね。