Am 09.03.2009 um 17:46 schrieb 7stud:
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.
Have a look at foldl.com and foldr.com. With "empty list element" they mean the 0.
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?
The problem is that foldr can lazyly produce a result. Try foldr (:) [] [1..]. It works. Now try foldl (flip (:)) [] [1..]. It breaks. However foldl is tail recursive, so the compiler can optimize the recursion away. In some cases that is beneficial. Notice that there is no difference between foldr g a foldl f a (for appropriate g and f) if g and f are strict in both arguments. Have a look at the "Foldl as foldr" wikipage. Also have a look at this paper
Regards, Adrian