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