2008年04月23日

[Haskell] foldl関数の動き

   このエントリーをはてなブックマークに追加 Clip to Evernote
Haskellのmaximum関数は,
maximum, minimum :: (Ord a) => [a] -> a
maximum [] = error "Prelude.maximum: empty list"
maximum xs = foldl1 max xs

という定義らしい。
ここで出てきた foldl1についても調べてみる。
foldl1の定義は、
foldl1           :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error "Prelude.foldl1: empty list"
foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

だ。

重要なのは、
 foldl f z (x:xs) =  foldl f (f z x) xs

の部分。
 foldl func z (x:xs)

という関数呼び出しのコードだと、
 func z x

の値を新たな z ととし、xs を新たな第3引数のリストとし、再帰的にfoldlを呼びだすというものだ。
こうすることで、f の結果を保持しながら、リストを順に処理できることになる。

具体的に見てみよう。たぶん以下のように推移するんだと思う。
maximum [1,5,3,4]
-> foldl1 max [1,5,3,4]
-> foldl max 0 [1,5,3,4]
-> foldl max (max 0 1) [5,3,4]
-> foldl max 1 [5,3,4]
-> foldl max (max 1 5) [3,4]
-> foldl max 5 [3,4]
-> foldl max (max 5 4) [4]
-> foldl max 5 [4]
-> foldl max (max 5 4) []
-> foldl max 5 []
-> 5

僕にはとても思いつきません。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51488958