7stud wrote:
This is an example that shows how foldl and foldr work (from RWH p.93-94):
foldl (+) 0 (1:2:3:[]) == foldl (+) (0 + 1) (2:3:[]) == foldl (+) ((0 + 1) + 2) (3:[]) == foldl (+) (((0 + 1) + 2) + 3) [] == (((0 + 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))
The book says on p.94:
----- The difference between foldl and foldr should be clear from looking at where the parentheses and the empty list elements show up. With foldl, the empty list element is on the left, and all the parentheses group to the left. With foldr, the zero value is on the right, and the parentheses group to the right. ----
Huh? With foldl, the only empty list element I see is on the right.
A fold like foldr f z is best understood as a function that replaces each (:) with f and each [] with z . See also the diagrams on http://en.wikipedia.org/wiki/Fold_(higher-order_function)
From this point of view, z "corresponds to the empty list".
Initially, it looked to me like they did the same thing, and that the only difference was the way they called step.
They are only the same when the operation f is associative, i.e. if it satisfies f x (f y z) = f (f x y) z
But then RWH explains that you would never use foldl in practice because it thunks the result, which for large lists can overwhelm the maximum memory alloted for a thunk. But it appears to me the same thunk problem would occur with foldr. So why is foldr used in practice but not foldl?
See also http://en.wikibooks.org/wiki/Haskell/Performance_Introduction#Space Regards, apfelmus -- http://apfelmus.nfshost.com