Mon Mar 9 13:24:07 EDT 2009

```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

> http://www.cs.nott.ac.uk/~gmh/fold.pdf

Regards,