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

foldr と foldl の定義

HaskellWiki/Fold を読んでいたら、foldr と foldl が簡単に再帰的定義で定義できるのが分かった。

そこで myfold.hs というファイルに次のように myfoldr と myfoldl を定義してみた。

ファイル名 : myfold.hs

myfoldr f z [] = z
myfoldr f z (x:xs) = f x (myfoldr f z xs)

myfoldl f z [] = z
myfoldl f z (x:xs) = myfoldl f (f z x) xs

これを ghci に load して実行してみたら、驚いたことに myfoldr がちゃんと foldr として動いた。
Prelude> :e myfold.hs
Prelude> :l myfold.hs
[1 of 1] Compiling Main
Ok, modules loaded: Main.
*Main> myfoldr (+) 0 [1..5]
15
*Main> myfoldl (*) 1 [1..5]
120

foldr の中身が再帰的定義として分かっていれば、動作の解析も簡単だ。myfoldr (+) 0 [1..5] を定義に従って展開すると次のようになる。

myfoldr (+) 0 [1,2,3,4,5]
= 1 + (myfoldr (+) 0 [2,3,4])
= 1 + (2 + (myfoldr (+) 0 [3,4]))
= 1 + (2 + (3 + (myfoldr (+) 0 [4,5])))
= 1 + (2 + (3 + (4 + (myfoldr (+) 0 [5]))))
= 1 + (2 + (3 + (4 + (5 + (myfoldr (+) 0 [])))))
= 1 + (2 + (3 + (4 + (5 + 0))))
= 15

この展開式を見ると foldr の値が計算を途中で中断してもそれまでの段階の値を得る事ができるのがわかる。したがって、foldr は無限リストに対しても適用できることが理解できる。これとは逆に foldl の場合は全ての式の展開が行われなければ部分的な値さえ得る事ができない。

foldr のような基本的な関数についても内部的な構造をユーザが知ることができるのが Haskell の良いところだ。
by tnomura9 | 2011-08-24 23:39 | Haskell | Comments(0)
<< Data.List モジュール... 機械に教わる >>