人気ブログランキング | 話題のタグを見る

Haskell あれこれ。foldr と foldl

Haskell 標準の Prelude ライブラリの高階関数のうちで、map と filter は直感的にわかりやすい。

Main> map (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
Main> filter (>5) [1..10]
[6,7,8,9,10]

しかし、foldr と foldl の使い方については最初悩んだ。しかし、これは数式に展開してみるとよく分かる。foldr op a [a] ののように、fold 高階関数は第1の引数に演算子、第2の引数に固定値、第3の引数にリストをとる。foldr は演算子の右に式を適用していく。つまり、次のような計算をしてくれる。

foldr op v [1..4] = (1 op (2 op (3 op (4 op v))))
演算子 op に引き算をする subtract 関数をとると上の式は、

foldr subtract 0 [1..4] = (1 - (2 - (3 - (4 - 0))))
= 2

foldl は演算子の左に式を展開していくので、

foldl subtract 0 [1..4] = ((((0 - 1) -2) - 3) -4)
= -15

foldr, foldl を使うとリストにいろいろな積算を加えることができる。

Main> foldr (+) 0 [1..5] -- sum [1..5] と同じ
15
Main> foldr (*) 1 [1..5] -- product [1..5] と同じ
120
Main> foldl (flip (:)) [] [1..5] -- reverse [1..5] と同じ
[5,4,3,2,1]
by tnomura9 | 2009-08-16 12:32 | Haskell | Comments(3)
Commented at 2011-06-29 19:59 x
ブログの持ち主だけに見える非公開コメントです。
Commented at 2011-06-30 12:38
ブログの持ち主だけに見える非公開コメントです。
Commented by tnomura9 at 2011-08-24 08:21
たぼとさん、コメントありがとうございました。左右を間違えていました。というよりfold の仕組み自体を理解していなかったようです。http://www.haskell.org/haskellwiki/Fold を参考に訂正しました。
<< Haskell あれこれ 無限... 2009年後半の記事 >>