関数型言語の場合、リスト操作関数の多くは高階関数として定義されています。今回はよく使われる高階関数として、マッピング、フィルター、畳み込み (縮約) について説明します。
まず最初に、リストの要素に関数 f を適用して、その結果をリストに格納して返す関数を作ってみましょう。このような操作を「マッピング (写像)」といいます。次のリストを見てください。
リスト : マッピング map' :: (a -> b) -> [a] -> [b] map' _ [] = [] map' f (x:xs) = f x : map' f xs
Haskell にはマッピングを行う関数 map が定義されているので、ここでは関数名を map' としました。プログラムは簡単です。パターンマッチングで引数のリストを先頭の要素 x と残りのリスト xs に分解します。
そして、x に関数 f を適用した結果と map' f xs の結果をコンス演算子 : で結合します。引数のリストが空リストの場合が再帰呼び出しの停止条件になります。
ここで map' の型に注目してください。第 1 引数が関数型 a -> b で第 2 引数がリスト [a] になります。関数 f はリストの要素を受け取るので、関数 f の引数の型とリストの型は一致します。これを型変数 a で表しています。
同様に、関数 f の返り値の型と map' の返り値のリストの型は一致します。これを型変数 b で表しています。このように、map' は多相型関数として定義されます。
簡単な実行例を示します。
ghci> map' (*2) [1,2,3,4,5] [2,4,6,8,10] ghci> map' (+10) [1,2,3,4,5] [11,12,13,14,15]
マップ関数を使うと前回作成した sum_of を簡単に定義することができます。
ghci> sum_of f n m = sum (map f [n .. m]) ghci> sum_of id 1 10 55 ghci> sum_of id 1 100 5050 ghci> sum_of (^2) 1 10 385 |
ghci> sum_of (^2) 1 100 338350 ghci> sum_of (^3) 1 10 3025 ghci> sum_of (^3) 1 100 25502500 |
[n .. m] で n 以上 m 以下の数列 (リスト) を生成し、map でその要素に関数 f を適用します。最後に、map で生成されたリストの要素の総和を sum で求めればいいわけです。とても簡単ですね。
「フィルター (filter)」はリストの要素に関数を適用し、関数が真を返す要素をリストに格納して返す関数です。真偽値を返す関数のことを「述語 (predicate)」といいます。ここでは簡単な例題として、述語が真を返す要素を削除する関数 remove_if を作ってみましょう。関数名は Common Lisp から拝借しました。
リスト : 要素の削除 remove_if :: (a -> Bool) -> [a] -> [a] remove_if _ [] = [] remove_if p (x:xs) | p x = remove_if p xs | otherwise = x : remove_if p xs
map' と同様に remove_if も簡単です。p x が真ならば x をリストに加えません。偽ならば x をリストに加えるだけです。remove_if の型ですが、述語 p は if の条件式で使われているので、型は a -> Bool となります。もちろん、remove_if も多相型関数として定義されます。簡単な実行例を示します。
ghci> remove_if even [1,2,3,4,5,6,7,8] [1,3,5,7] ghci> remove_if (== "abc") ["abcd", "abc", "ab", "a"] ["abcd","ab","a"]
最初の例では偶数の要素が削除されます。次の例は文字列 "abc" が削除されます。
もちろん、フィルターも簡単に定義することができます。remove_if とは逆に、述語が真を返すとき要素をリストに追加し、偽を返すときはリストに加えません。なお、Haskell には同様の動作を行う関数 filter が定義されているので、ここでは関数名を filter' としました。
リスト : フィルター filter' :: (a -> Bool) -> [a] -> [a] filter' _ [] = [] filter' p (x:xs) | p x = x : filter' p xs | otherwise = filter' p xs
簡単な実行例を示しましょう。
ghci> filter' even [1,2,3,4,5,6,7,8] [2,4,6,8] ghci> filter' (== "abc") ["abcd", "abc", "ab", "a"] ["abc"] ghci> filter' (/= "abc") ["abcd", "abc", "ab", "a"] ["abcd","ab","a"]
2 つの引数を取る関数 f とリストを引数に受け取る関数 reduce を考えます。reduce はリストの各要素に対して関数 f を下図のように適用します。
(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 ) ) ) )
図 : 関数 reduce の動作
関数 f を適用する順番で 2 通りの方法があります。図 (1) はリストの先頭から f を適用し、図 (2) はリストの後ろから f を適用します。たとえば、関数 f が単純な加算関数とすると、reduce の結果はどちらの場合もリストの要素の和になります。
f(x, y) = x + y の場合 reduce => a1 + a2 + a3 + a4 + a5
このように、reduce はリストのすべての要素を関数 f を用いて結合します。このような操作を「縮約」とか「畳み込み」といいます。また、reduce の引数に初期値 g を指定することがあります。この場合、reduce は下図に示す動作になります。
(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 ) ) ) ) )
図 : reduce の動作 (2)
ここでは簡単な例題として、上図 (1) の動作を行う関数 fold_left と、(2) の動作を行う関数 fold_right を作ってみましょう。なお、Haskell には同様の動作を行う関数 foldl と foldr があります。
プログラムは次のようになります。
リスト : 畳み込み fold_left :: (a -> b -> a) -> a -> [b] -> a fold_left _ a [] = a fold_left f a (x:xs) = fold_left f (f a x) xs fold_right :: (a -> b -> b) -> b -> [a] -> b fold_right _ a [] = a fold_right f a (x:xs) = f x (fold_right f a xs)
第 1 引数 f が適用する関数、第 2 引数 a が初期値、第 3 引数がリストです。最初の節は再帰呼び出しの停止条件ですが、fold_left (fold_right) に空リストが与えられた場合にも対応します。この場合は初期値 a を返します。次の節でリストの要素を取り出して関数 f を呼び出します。
たとえば、リストが [1, 2, 3] で a が 0 とします。最初は f(0, 1) が実行され、その返り値が fold_left の第 2 引数に渡されます。次は f(a, 2) が実行されますが、これは f(f(0, 1), 2) と同じことです。そして、その結果が fold_left の第 2 引数になります。最後に f(a, 3) が実行されますが、これは f(f(f(0, 1), 2), 3) となり、図 (1) と同じ動作になります。
fold_left の場合、リストの要素が関数 f の第 2 引数になり、第 1 引数にはこれまでの処理結果が渡されます。これに対し、fold_right の場合は逆になり、関数 f の第 1 引数にリストの要素が渡されて、これまでの処理結果は第 2 引数に渡されます。これで図 (2) の動作を実現することができます。
ここで型を見てみましょう。fold_left と fold_right の返り値は初期値 a の型と同じになります。つまり、リストの要素と同じ型である必要はありません。そして、渡される関数の型にも注目してください。fold_left の場合、関数の第 1 引数と初期値の型が同じです。第 1 引数に今までの処理結果が渡されて、第 2 引数にリストの要素が渡されることがわかります。これに対し、fold_right は逆になっていることに注意してください。
簡単な実行例を示します。
ghci> fold_left (+) 0 [1,2,3,4,5] 15 ghci> fold_right (+) 0 [1,2,3,4,5] 15
どちらの例もリストの要素の総和を求めています。畳み込みを使うと、関数 sum は次のように定義することができます。
リスト : 要素の総和を求める sum' :: Num a => [a] -> a sum' xs = fold_left (+) 0 xs
このほかにも、畳み込みと 2 引数の関数を組み合わせると、いろいろな関数を実現することができます。最初に length の例を示します。
ghci> let length' xs = fold_left (\a _ -> a + 1) 0 xs ghci> length' [] 0 ghci> length' [1,2,3,4,5] 5
fold_left で length を実現する場合、初期値を 0 にしてラムダ式の第 1 引数 a を +1 することで実現できます。
次に map の例を示します。
ghci> let map' f xs = fold_right (\x a -> f x : a) [] xs ghci> map' (^2) [1,2,3,4,5] [1,4,9,16,25]
map は fold_rigth を使うと簡単です。初期値を [ ] にしてラムダ式の第 1 引数に関数 f を適用した結果を第 2 引数のリストに追加するだけです。
次に filter の例を示します。
ghci> let filter' p xs = fold_right (\x a -> if p x then x:a else a) [] xs ghci> filter' even [1,2,3,4,5,6,7,8] [2,4,6,8] ghci> filter' odd [1,2,3,4,5,6,7,8] [1,3,5,7]
filter の場合も初期値を [ ] にして、ラムダ式の第 1 引数が条件を満たしていれば第 2 引数のリストに追加します。
最後に述語が真となる要素の個数を求めてみましょう。これは Common Lisp の関数 count-if と同じです。
ghci> let count_if p xs = fold_left (\a x -> if p x then a + 1 else a) 0 xs ghci> count_if even [1,2,3,4,5,6,7] 3 ghci> count_if odd [1,2,3,4,5,6,7] 4
このように、畳み込みを使っていろいろな処理を実現することができます。
Hakell でリストを操作する場合、高階関数だけではなく「リスト内包表記 (List Comprehensions)」を使うことができます。基本的な構文を次に示します。
[式 | パターン <- 式, 条件式]
角カッコ [ ] の最初にリストの要素を生成する式を記述します。次に縦線 ( | ) で区切ったあと、"パターン <- 式" を記述します。これを「生成器」と呼ぶことにします。式の値はリストでなければなりません。式はリストをそのまま指定してもかまいません。<- はリストの先頭から順番に要素を取り出し、パターンとマッチングを行います。また、カンマで区切ったあと、条件式を指定することができます。
簡単な例を示しましょう。
ghci> [x * x | x <- [1 .. 10]] [1,4,9,16,25,36,49,64,81,100] ghci> [x * x | x <- [1 .. 10], even x] [4,16,36,64,100] ghci> [x * x | x <- [1 .. 10], odd x] [1,9,25,49,81]
最初の例は要素を 2 乗したリストを生成します。次の例は、偶数の要素を取り出して 2 乗します。最後の例は奇数の要素を取り出して 2 乗します。これらの動作は map や filter と同じです。
リスト内包表記は複数の生成器を指定することもできます。次の例を見てください。
ghci> [(x,y) | x <- [1,2,3], y <- [4,5,6]] [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
最初に、x が 1 とマッチングし、次に y がリスト [4, 5, 6] の要素とマッチングして、タプル (1,4), (1,5), (1,6) が生成され生ます。次に、x の値が 2 に束縛されてから再度 y と [4, 5, 6] のマッチングが動作するので、タプル (2,4), (2,5), (2,6) が生成されます。最後に、x が 3 に束縛されてタプル (3,4), (3,5), (3,6) が生成されます。
また、それぞれの生成器のあとに条件式を設定することもできます。簡単な例を示します。
ghci> [(x, y) | x <- [1..10], even x, y <- [1..10], odd y] [(2,1),(2,3),(2,5),(2,7),(2,9),(4,1),(4,3),(4,5),(4,7),(4,9),(6,1),(6,3),(6,5), (6,7),(6,9),(8,1),(8,3),(8,5),(8,7),(8,9),(10,1),(10,3),(10,5),(10,7),(10,9)]
タプルの第 1 要素 x は偶数、第 2 要素 y は奇数になります。
それでは簡単な例題として、リスト内包表記を使ってクイックソートを書き直してみましょう。
リスト : クイックソート
quick_sort' :: Ord a => [a] -> [a]
quick_sort' [] = []
quick_sort' (x:xs) = quick_sort' [y | y <- xs, y < x]
++ [x]
++ quick_sort' [y | y <- xs, y >= x]
引数のリストが空リストであれば空リストを返します。そうでなければ、リストの先頭要素 x を枢軸として、リスト内包表記で x より小さい要素と x 以上の要素に分けます。あとは quick_sort を再帰呼び出しして、その結果を [x] をはさんで演算子 ++ で連結するだけです。ただし、リスト xs を二分割するとき、xs を 2 回走査することに注意してください。
もうひとつ簡単な例題として、リストを平坦化する関数 flatten を作ってみましょう。なお、Haskell には同じ働きをする関数 concat が用意されています。簡単な動作例を示します。
ghci> flatten [[1,2,3],[4,5,6],[7,8,9]] [1,2,3,4,5,6,7,8,9] ghci> flatten [[1,2,3],[],[4,5,6],[],[7,8,9]] [1,2,3,4,5,6,7,8,9]
プログラムは次のようになります。
リスト : リストの平坦化 flatten :: [[a]] -> [a] flatten [] = [] flatten (x:xs) = x ++ flatten xs -- リスト内包表記 flatten' :: [[a]] -> [a] flatten' xss = [x | xs <- xss, x <- xs]
flatten はリストの先頭要素 x を取り出して、x と次の要素を演算子 ++ で結合すればいいわけです。リスト内包表記を使うともっと簡単になります。リスト xss から要素 xs を取り出し、xs からさらに要素 x を取り出します。あとは、x をリストに格納して返すだけです。
次の関数を定義してください。
リスト : 解答例 (q05.hs)
maplist :: ([a] -> b) -> [a] -> [b]
maplist _ [] = []
maplist fn xs@(_:ys) = fn xs : maplist fn ys
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' fn (x:xs) (y:ys) = fn x y : zipWith' fn xs ys
count_if :: (a -> Bool) -> [a] -> Int
count_if _ [] = 0
count_if pred (x:xs) = (if pred x then 1 else 0) + count_if pred xs
scan_left :: (a -> b -> a) -> a -> [b] -> [a]
scan_left _ a [] = [a]
scan_left fn a (x:xs) = a : scan_left fn (fn a x) xs
scan_right :: (a -> b -> b) -> b -> [a] -> [b]
scan_right _ a [] = [a]
scan_right fn a (x:xs) =
let
ys = scan_right fn a xs
in
fn x (head ys) : ys
ghci> :l q05.hs [1 of 1] Compiling Main ( q05.hs, interpreted ) Ok, one module loaded. ghci> maplist id [10,20,30,40,50] [[10,20,30,40,50],[20,30,40,50],[30,40,50],[40,50],[50]] ghci> maplist length [1,2,3,4,5] [5,4,3,2,1] ghci> zipWith' (+) [1,2,3,4,5] [6,7,8,9,10] [7,9,11,13,15] ghci> zipWith' (*) [1,2,3,4,5] [6,7,8,9,10] [6,14,24,36,50] ghci> count_if even [1 .. 11] 5 ghci> count_if odd [1 .. 11] 6 ghci> count_if (<4) [1 .. 11] 3 ghci> count_if (>4) [1 .. 11] 7 ghci> scan_left (+) 0 [1 .. 10] [0,1,3,6,10,15,21,28,36,45,55] ghci> scan_left (*) 1 [1 .. 10] [1,1,2,6,24,120,720,5040,40320,362880,3628800] ghci> scan_right (+) 0 [1 .. 10] [55,54,52,49,45,40,34,27,19,10,0] ghci> scan_right (*) 1 [1 .. 10] [3628800,3628800,1814400,604800,151200,30240,5040,720,90,10,1]
scan_left はリストの最後の要素が最終の累積値になります。xs が空リストのとき、累積変数 a の値をリストに格納して返します。そうでなければ、scan_left を再帰呼び出しして、その返り値に累積変数 a の値を追加して返します。scan_left を再帰呼び出しするときは、関数 fn を呼び出して累積変数の値を更新することに注意してください。
scan_right はリストの先頭の要素が最終の累積値、最後の要素が初期値になります。第 3 引数が空リストの場合は [a] を返します。そうでなければ、scan_right を再帰呼び出しします。このとき、累積変数 a の値は更新しません。返り値のリストは変数 ys にセットします。この ys の先頭要素が一つ前の累積値になるので、この値とリストの要素 x を関数 fn に渡して評価します。あとは、fn の返り値を ys の先頭に追加して返せばいいわけです。