TIM Labs

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

| コメント(0) | トラックバック(0)
『関数プログラミング』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 の屁理屈を述べたに過ぎない。
限りなく無意味な例ではないだろうか。

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


トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/329

コメントする

このブログ記事について

このページは、fujiが2012年11月20日 10:00に書いたブログ記事です。

ひとつ前のブログ記事は「ピタゴラス数は超高速で求まる」です。

次のブログ記事は「Haskellは分数がお得意(eの計算)」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。