foldr と foldl

Haskell(Prelude) の標準関数の foldr (右畳み込み)は分かりにくい関数だが、これも式の展開で考えると分かりやすくなる。

foldr 関数は便利な関数で、リストの要素の総和を求める sum [1,2,3] のような関数も、sum = foldr (+) 0 で定義することができる。またリストの要素の積を求める関数 product [1,2,3] のようなものも、product = foldr (*) 1 で定義できる。便利な関数なのだが、畳み込みという動作は必ずしも分かりやすいものではない。

しかし、これも関数の展開をシミュレーションしてみると分かりやすくなる。foldr の定義は次のようになる。

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

foldr (+) 0 [1,2,3] を展開していくと次のような結果になるが、これはリスト [1,2,3] の総和を計算していることになる。

foldr (+) 0 [1,2,3]
= 1 + (foldr (+) 0 [2,3])
= 1 + (2 + (foldr (+) 0 [3]))
= 1 + (2 + (3 + (foldr (+) 0 [])))
= 1 + (2 + (3 + 0))
= 6

foldr の他に foldl (左畳み込み)という関数がある。この関数の定義は次のようになる。

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

foldl (+) 0 [1,2,3] の展開は次のようになる。

foldl (+) 0 [1,2,3]
= foldl (+) (0 + 1) [2,3]
= foldl (+) ((0 + 1) + 2) [3]
= foldl (+) (((0 + 1) + 2) + 3) []
= ((((0 + 1) +2) + 3) + 0)
= 6

この例では、foldr も foldl も同じ結果になってしまうが、次のような例では差がはっきりする。

foldr (\x y -> x + 2*y) 0 [1,0,1]
= 1 + 2*(foldr (\x y -> x + 2*y) 0 [0,1])
= 1 + 2*(0 + 2*(foldr (\x y -> x +2*y) 0 [1]))
= 1 + 2*(0 + 2*(1 + 2*(foldr (\x y -> x + 2*y) 0 [])))
= 1 + 2*(0 + 2*(1 + 2*0))
= 1 + 2*0 + 4*1
= 5

これは、リストを昇順の2進数表記とみなして整数に変換するプログラムになっている。foldl の場合は次のようになる。

foldl (\x y -> 2*x + y) 0 [1,1,0]
= foldl (/x y -> 2*x + y) (2*0 + 1) [1,0]
= foldl (/x y -> 2*x + y) (2*(2*0 + 1) + 1) [0]
= foldl (/x y -> 2*x + y) (2*(2*(2*0 + 1) +1) + 0) []
= 2*(2*(2*0 + 1) + 1) +0
= 4*1 + 2*1 + 0
= 6

これは、リストを降順の2進数表記とみなして整数に変換している。

このように、Haskellの動作は式の展開で説明できる。
[PR]
by tnomura9 | 2010-10-10 22:23 | Haskell | Comments(0)
<< 関数のカリー化も式の置き換え リストの総和も式の展開で計算 >>