foldr
[id:lethevert:20051011:p1]
で、よく分からないとかいたけれど、展開してみたら、分かった。
foldlは、確かに、計算量が増えることがある。
ところで、Concurrent Cleanのfoldr/foldlの定義は、効率性のために、ちょっと分かりづらくなっているけれど、
// foldl :: (.a -> .(.b -> .a)) .a ![.b] -> .a // op(...(op (op (op r e0) e1)...e##) foldl op r l :== foldl r l where foldl r [] = r foldl r [a:x] = foldl (op r a) x // foldr :: (.a -> .(.b -> .b)) .b ![.a] -> .b // op e0 (op e1(...(op e## r)...) foldr op r l :== foldr l where foldr [] = r foldr [a:x] = op a (foldr x)
Haskellの定義は分かりやすいと思う。
foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs foldl' f z [] = z foldl' f z (x:xs) = (foldl' f $! f z x) xs