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 の関数は引数を 5 倍した結果を返すのです。
また、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 は「高階関数」で説明した畳み込み (fold_left, fold_right) と同じ働きをする関数です。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 の動作は「高階関数」で説明した fold_left の動作と少し異なります。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 は引数の述語が真となる要素の個数を数える関数です。匿名関数 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 pred l は述語 pred が真となる要素をリストに格納して返す関数で、remove_if と逆の働きをします。find pred l は述語 pred が真となる要素を探す関数です。exists pred l は述語 pred を満たす要素が一つでもあれば真を返し、そうでない場合は偽を返します。逆に、all pred l は全ての要素が述語 pred を満たせば真を返し、述語 pred を満たさない要素が一つでもあれば偽を返します。簡単な使用例を示します。
- 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 は関数を柔軟に操作することができます。