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