bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskell ドリル15 foldl関数と遅延評価

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までの奇数である。
f:id:bitterharvest:20141213214922p:plain

ここでの演算は加算なので、第一引数の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を用いて求めなさい。