[Haskell-beginners] folds -- help!

[Adrian Neumann]

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,

Adrian

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 194 bytes
Desc: Signierter Teil der Nachricht
Url : http://www.haskell.org/pipermail/beginners/attachments/20090309/a5bb8304/PGP.bin