関数型言語の場合、リスト操作関数の多くは高階関数として定義されています。今回はよく使われる高階関数として、マッピング、フィルター、畳み込み (縮約) について説明します。
まず最初に、リストの要素に関数 f を適用して、その結果をリストに格納して返す関数を作ってみましょう。このような操作を「マッピング (写像)」といいます。次のリストを見てください。
リスト 6 : マッピング let rec mapcar f = function [] -> [] | x :: xs -> f x :: mapcar f xs
関数名は mapcar としました。名前は Common Lisp から拝借しました。なお、OCaml には同じ機能を持つ関数 List.map があります。
プログラムは簡単です。パターンマッチングで引数のリストを先頭の要素 x と残りのリスト xs に分解します。そして、x に関数 f を適用した結果と mapcar f xs の結果をコンス演算子 :: で結合します。引数のリストが空リストの場合が再帰呼び出しの停止条件になります。
mapcar を定義すると、次のように表示されます。
val mapcar : ('a -> 'b) -> 'a list -> 'b list = <fun>
第 1 引数が関数型 'a -> 'b で第 2 引数がリスト 'a list になります。関数 f はリストの要素を受け取るので、関数 f の引数の型とリストの型は一致します。これを型変数 'a で表しています。同様に、関数 f の返り値の型と mapcar の返り値のリストの型は一致します。これを型変数 'b で表しています。このように、mapcar は多相型関数として定義されます。
簡単な実行例を示します。
# mapcar (fun x -> x * x) [1; 2; 3; 4; 5];; - : int list = [1; 4; 9; 16; 25]
フィルター (filter) はリストの要素に関数を適用し、関数が真を返す要素をリストに格納して返す関数です。真または偽を返す関数のことを「述語 (predicate)」といいます。ここでは簡単な例題として、述語が真を返す要素を削除する関数 remove_if を作ってみましょう。名前は Common Lisp から拝借しました。
リスト 7 : 要素の削除 let rec remove_if f = function [] -> [] | x :: xs -> if f x then remove_if f xs else x :: remove_if f xs
mapcar と同様に remove_if も簡単です。f x が真ならば x をリストに加えません。偽ならば x をリストに加えるだけです。remove_if を定義すると次のようになります。
val remove_if : ('a -> bool) -> 'a list -> 'a list = <fun>
関数 f が if の条件式で使われているので、OCaml は関数 f の型を 'a -> bool と推論しています。もちろん、remove_if も多相型関数として定義されます。OCaml の型推論はとても便利ですね。簡単な実行例を示します。
# remove_if (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5];; - : int list = [1; 3; 5] # remove_if (fun x -> x = "abc") ["abc"; "def"; "abc"; "ghi"];; - : string list = ["def"; "ghi"]
最初の例では偶数の要素が削除されます。次の例は文字列 "abc" が削除されます。
もちろん、フィルターも簡単に定義することができます。remove_if とは逆に、述語が真を返すとき要素をリストに追加し、偽を返すときはリストに加えません。なお、OCaml には同様の動作を行う関数 List.filter があります。
リスト 8 : フィルター let rec filter f = function [] -> [] | x :: xs -> if f x then x :: filter f xs else filter f xs
簡単な実行例を示しましょう。
# filter (fun x -> x mod 2 = 0) [1;2;3;4;5];; - : int list = [2; 4]
2 つの引数を取る関数 f とリストを引数に受け取る関数 reduce を考えます。reduce はリストの各要素に対して関数 f を図 1 のように適用します。
(1) [a1; a2; a3; a4; a5]
=> f( f( f( f( a1, a2 ), a3 ), a4 ), a5 )
(2) [a1; a2; a3; a4; a5]
=> f( a1, f( a2, f( a3, f( a4, a5 ) ) ) )
図 1 : 関数 reduce の動作
関数 f を適用する順番で 2 通りの方法があります。図 1 (1) はリストの先頭から f を適用し、図 1 (2) はリストの後ろから f を適用します。たとえば、関数 f が単純な加算関数とすると、reduce の結果はどちらの場合もリストの要素の和になります。
f(x, y) = x + y の場合 reduce => a1 + a2 + a3 + a4 + a5
このように、reduce はリストのすべての要素を関数 f を用いて結合します。このような操作を「縮約」とか「畳み込み」といいます。また、reduce の引数に初期値 g を指定することがあります。この場合、reduce は図 2 に示す動作になります。
(1) [a1; a2; a3; a4; a5]
=> f( f( f( f( f( g, a1 ), a2 ), a3 ), a4 ), a5 )
(2) [a1; a2; a3; a4; a5]
=> f( a1, f( a2, f( a3, f( a4, f( a5, g ) ) ) ) )
図 2 : reduce() の動作 (2)
ここでは簡単な例題として、図 2 (1) の動作を行う関数 reduce と、図 2 (2) の動作を行う関数 reduce_right を作ってみましょう。なお、OCaml には同様の動作を行う関数 List.fold_left と List.fold_right があります。
プログラムは次のようになります。
リスト 9 : 畳み込み let rec reduce f a = function [] -> a | x :: xs -> reduce f (f a x) xs let rec reduce_right f a = function [] -> a | x :: xs -> f x (reduce_right f a xs)
第 1 引数 f が適用する関数、第 2 引数 a が初期値、第 3 引数がリストです。最初のマッチング節は再帰呼び出しの停止条件ですが、reduce (reduce_right) に空リストが与えられた場合にも対応します。この場合は初期値 a を返します。次のマッチング節でリストの要素を取り出して関数 f を呼び出します。
たとえば、リストが [1; 2; 3] で a が 0 とします。最初は f(0, 1) が実行され、その返り値が reduce の第 2 引数に渡されます。次は f(a, 2) が実行されますが、これは f(f(0, 1), 2) と同じことです。そして、その結果が reduce の第 2 引数になります。最後に f(a, 3) が実行されますが、これは f(f(f(0, 1), 2), 3) となり、図 2 (1) と同じ動作になります。
reduce の場合、リストの要素が関数 f の第 2 引数になり、第 1 引数にはこれまでの処理結果が渡されます。これに対し、reduce_right の場合は逆になり、関数 f の第 1 引数にリストの要素が渡されて、これまでの処理結果は第 2 引数に渡されます。これで図 2 (2) の動作を実現することができます。
それでは、reduce と reduce_right の型を示します。
val reduce : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
val reduce_right : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b
reduce と reduce_right の返り値は初期値 a の型と同じになります。つまり、リストの要素と同じ型である必要はありません。そして、渡される関数の型にも注目してください。reduce の場合、関数の第 1 引数と初期値の型が同じです。第 1 引数に今までの処理結果が渡されて、第 2 引数にリストの要素が渡されることがわかります。これに対し、reduce_right は逆になっていることに注意してください。
簡単な実行例を示します。
# reduce (fun x y -> x + y) 0 [1; 2; 3; 4; 5];; - : int = 15 # reduce_right (fun x y -> x + y) 0 [1; 2; 3; 4; 5];; - : int = 15
ところで、reduce, reduce_right と 2 引数の関数を組み合わせると、いろいろな関数を実現することができます。最初に length の例を示します。
# reduce (fun x y -> x + 1) 0 [0; 1; 2; 3; 4; 5];; - : int = 6 # reduce_right (fun x y -> y + 1) 0 [0; 1; 2; 3; 4; 5];; - : int = 6
reduce で length を実現する場合、初期値を 0 にして第 1 引数の値を +1 することで実現できます。reduce_right の場合は第 2 引数の値を +1 します。
次に map の例を示します。
# reduce_right (fun x y -> (x * x)::y) [] [1; 2; 3; 4; 5];; - : int list = [1; 4; 9; 16; 25]
map の場合は reduce_rigth を使うと簡単です。初期値を [ ] にして第 1 引数の計算結果を第 2 引数のリストに追加するだけです。
次に filter の例を示します。
# reduce_right (fun x y -> if x mod 2 = 0 then x::y else y) [] [1; 2; 3; 4; 5];; - : int list = [2; 4]
filter の場合も初期値を [ ] にして、第 1 引数が条件を満たしていれば第 2 引数のリストに追加します。
最後に述語が真となる要素の個数を求めてみましょう。これは Common Lisp の関数 count-if と同じです。
# reduce (fun x y -> if y mod 2 = 0 then x + 1 else x) 0 [1; 2; 3; 4; 5] - : int = 2
このように、畳み込みを使っていろいろな処理を実現することができます。
次に示す高階関数を定義していください。
リスト : 解答例
let rec tabulate fn s e =
if s > e then []
else fn s :: tabulate fn (s + 1) e
let rec foreach fn = function
[] -> ()
| x::xs -> begin fn x; foreach fn xs end
let rec maplist fn = function
[] -> []
| _::ys as xs -> fn xs :: maplist fn ys
let rec take_while pred = function
x::xs when pred x -> x :: take_while pred xs
| _ -> []
let rec drop_while pred = function
x::xs when pred x -> drop_while pred xs
| xs -> xs
let rec scan_left fn a = function
[] -> [a]
| x::xs -> a :: scan_left fn (fn a x) xs
let rec scan_right fn a = function
[] -> [a]
| x::xs -> let ys = scan_right fn a xs in fn x (List.hd ys) :: ys
val tabulate : (int -> 'a) -> int -> int -> 'a list = <fun>
val foreach : ('a -> 'b) -> 'a list -> unit = <fun>
val maplist : ('a list -> 'b) -> 'a list -> 'b list = <fun>
val take_while : ('a -> bool) -> 'a list -> 'b list = <fun>
val drop_while : ('a -> bool) -> 'a list -> 'a list = <fun>
val scan_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a list = <fun>
val scan_right : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b list = <fun>
# tabulate (fun x -> x) 1 10;; - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] # tabulate (fun x -> x * x) 1 10;; - : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100] # tabulate (fun x -> x * x * x) 1 10;; - : int list = [1; 8; 27; 64; 125; 216; 343; 512; 729; 1000] # foreach print_int [1; 2; 3; 4; 5];; 12345- : unit = () # foreach (fun x -> begin print_int x; print_newline() end) [1; 2; 3; 4; 5];; 1 2 3 4 5 - : unit = () # maplist (fun x -> x) [1; 2; 3; 4; 5];; - : int list list = [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]] # maplist List.length [1; 2; 3; 4; 5];; - : int list = [5; 4; 3; 2; 1] # take_while (fun x -> x mod 2 = 0) [2; 4; 6; 8; 1; 3; 5; 7];; - : int list = [2; 4; 6; 8] # take_while (fun x -> x mod 2 = 0) [1; 3; 5; 7];; - : int list = [] # take_while (fun x -> x mod 2 = 1) [1; 3; 5; 7];; - : int list = [1; 3; 5; 7] # drop_while (fun x -> x mod 2 = 0) [2; 4; 6; 8; 1; 3; 5; 7];; - : int list = [1; 3; 5; 7] # drop_while (fun x -> x mod 2 = 0) [1; 3; 5; 7];; - : int list = [1; 3; 5; 7] # drop_while (fun x -> x mod 2 = 1) [1; 3; 5; 7];; - : int list = [] # scan_left (fun x y -> x + y) 0 [1;2;3;4;5;6;7;8;9;10];; - : int list = [0; 1; 3; 6; 10; 15; 21; 28; 36; 45; 55] # scan_left (fun x y -> x * y) 1 [1;2;3;4;5;6;7;8;9;10];; - : int list = [1; 1; 2; 6; 24; 120; 720; 5040; 40320; 362880; 3628800] # scan_left (fun x y -> x::y) [] [1;2;3;4;5];; - : int list list = [[]; [1]; [2; 1]; [3; 2; 1]; [4; 3; 2; 1]; [5; 4; 3; 2; 1]] # scan_right (fun x y -> x + y) 0 [1;2;3;4;5;6;7;8;9;10];; - : int list = [55; 54; 52; 49; 45; 40; 34; 27; 19; 10; 0] # scan_right (fun x y -> x::y) [] [1;2;3;4;5];; - : int list list = [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]; []]
scan_left はリストの最後の要素が最終の累積値になります。xs が空リストのとき、累積変数 a の値をリストに格納して返します。そうでなければ、scan_left を再帰呼び出しして、その返り値に累積変数 a の値を追加して返します。scan_left を再帰呼び出しするときは、関数 fn を呼び出して累積変数の値を更新することに注意してください。
scan_right はリストの先頭の要素が最終の累積値、最後の要素が初期値になります。リスト xs が空リストの場合は [a] を返します。そうでなければ、scan_right を再帰呼び出しします。このとき、累積変数 a の値は更新しません。返り値のリストは変数 ys にセットします。この ys の先頭要素が一つ前の累積値になるので、この値とリストの先頭要素 x を関数 fn に渡して評価します。あとは、fn の返り値を ys の先頭に追加して返せばいいわけです。