1.概略
Haskellには便利な関数が沢山そろっているが、その中でも、優れたものの一つは、foldlである。これは、左畳み込みともいわれる。与えられた演算をリストの要素ごとに施し、それを初期値に畳み込むのがfoldlである。
foldlは三つの引数を取る。第一引数は畳み込みに用いる演算である。第二引数は初期値である。第三引数はリストである。foldlの型シグネチャは次のようになっている。
Prelude> :t foldl foldl :: (b -> a -> b) -> b -> [a] -> b
ここで、bは初期値の型変数、aはリストの要素の型変数である。これらが関数への入力となる。出力は初期値と同じ型となる。
また、演算に使われる関数(b -> a -> b)は、第一引数が初期値と同じ型であり、第二引数がリストの要素と同じ型で、これらがこの関数への入力となって、出力は初期値と同じ型となる。
今、foldl (+) 0 [1,3,5,7] の動作を下図に示す。畳み込みの演算は加算である。また、初期値は0である。リストは1から7までの奇数である。
ここでの演算は加算なので、第一引数の0は「アキュムレータ」への初期値と見なしてよい。計算はリストの値をアキュムレータに畳み込むことである。foldlでは、リストの左側から畳み込んでいくので、最初に1がアキュムレータに送られる。しかし、Haskellではこの演算は遅延評価で行われる。即ち、値が必要になるまで、実際の計算は行われない。そのため、アキュムレータに1が送られた後でも、0と1の加算は行われず、0+1としてアキュムレータに蓄えられる。これは、最後の数が入るまで続く。最後に7が送られてきたとき初めて加算が行われる。
foldrは、foldlとは異なり、右側から畳み込みを行う。foldrの引数は、foldlと同じである。しかし、第一引数の関数が有する引数は、相互に逆になっている。即ち、foldrの場合には、第一引数の関数が有する第一引数はリストの要素と同じ型であり、第二引数は初期値と同じ型である。foldrの型シグネチャは次のようになっている。
Prelude> :t foldr foldr :: (a -> b -> b) -> b -> [a] -> b
2.例題
問題:foldrを用いて、10未満の奇数の合計を求めなさい。
解は次のようになる。
Prelude> foldr (+) 0 [1,3..10] 25
3.問題
それでは、foldl, foldrに関する問題を解いてみる。
問題1:出力を求めなさい。
Prelude> foldr (:) ['a','b','c','d'] []
問題2:出力を求めなさい。
Prelude> foldl (\a x -> a + x * x) 0 [1..5]
問題3:出力を求めなさい。
Prelude> foldr (\x a -> x * x + a) 0 [1..5]
問題4:出力を求めなさい。
Prelude> foldl (++) "" ["a","b","c","d"]
問題5:出力を求めなさい。
Prelude> foldl (\ a (x, y) -> a + x + y) 0 [(1,2),(3,4),(5,6),(7,8),(9,10)]
問題6:出力を求めなさい。
Prelude> foldr (\ (x, y) a -> x + y + a) 0 [(1,2),(3,4),(5,6),(7,8),(9,10)]
問題7:出力を求めなさい。
Prelude> foldl (&&) True [True, False, True, True]
問題8:出力を求めなさい。
Prelude> foldr (||) True [True, False, True, True]
問題9:10未満の偶数の和をfoldlを用いて求めなさい。
問題10:10未満の偶数の和をfoldrを用いて求めなさい。