[Haskell-beginners] Re: folds -- help!

[Heinrich Apfelmus]

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