畳み込み(fold)関数の使い道は?


2012年 11月 20日

『関数プログラミング』4.5 畳み込み(fold)関数

Haskellでとても重要なのが畳み込み関数であろう。Haskells.jpgのサムネール画像

リスト [x1,x2,x3,x4] が与えられたとき、

x1 ★ (x2 ★ (x3 ★ (x4 ★ e)))

の計算をしたくなることがある。★は何らかの2項演算子。

このように、右から順番にくくっていく演算をリストに対して行うのが右畳み込み関数 foldr である。
この定義は以下のようにされている。

foldr            :: (a -> b -> b ) -> b -> [a] -> b
foldr f e []     = e
foldr f e (x:xs) = f x (foldr f e xs)

そして、以上のことを右側からではなく、左側から処理していくのが foldl だ。

foldl            :: (b -> a -> b ) -> b -> [a] -> b
foldl f e []     = e
foldl f e (x:xs) = foldl (f e x) xs

しかし、これでは、わかり辛いだろう。
だから、実例がネッと上に結構転がっている。

foldlとfoldrの比較をするのに、(+) を使っているのをよく見る。

たとえば、リスト [1..10] の和を求めるのに、

Prelude> foldl (+) 0 [1..10]
55
Prelude> foldr (+) 0 [1..10]
55

として、結合法則が成り立つ演算の場合に、foldr と foldl の結果が同じだと。

結合法則が成り立たない例として、 (-) を使ったのをよく見かける。

Prelude> foldl (-) 0 [1..10]
-55
Prelude> foldr (-) 0 [1..10]
-5

これは、

(..(0)-1)-2)-3)-4)-5)-6)-7)-8)-9)-10
0-(1-(2-(3-(4-(5-(6-(7-(8-(9-(10)..)

の差に他ならない。つまらない、無理矢理な例に過ぎない。

こんな説明をされても嬉しくない。
これでは、foldr や foldl の屁理屈を述べたに過ぎない。
限りなく無意味な例ではないだろうか。

もっと有用な使い道がきっとあるはずだ。
考えてみよう。