[Haskell-beginners] Re: folds -- help!
apfelmus at quantentunnel.de
Tue Mar 10 14:31:50 EDT 2009
> 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
> 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
>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
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?
More information about the Beginners