[Haskell-beginners] folds -- help!

7stud bbxx789_05ss at yahoo.com
Mon Mar 9 12:46:16 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
right.
----

Huh?  With foldl, the only empty list element I see is on the right.

Initially, it looked to me ike they did the same thing, and that the only 
difference was the way they called step.  I think "step" is a horrible, 
non-descriptive name, so I'm going to use "accFunc" instead:

foldl calls: accFunc acc x

foldr calls: accFunc x acc

So it looks like you can define a function using either one and get the
same result.  Here is a test:

--I am going to use odd for pfunc and [1, 2, 3] for xs:

myFilter1 pfunc xs = foldl accFunc [] xs
    where accFunc acc x  
            | pfunc x       = acc ++ [x]
            | otherwise     = acc

myFilter2 pfunc xs = foldr accFunc [] xs
    where accFunc x acc
            | pfunc x       = acc ++ [x]
            | otherwise     = acc


*Main> myFilter1 odd [1, 2, 3]
[1,3]
*Main> myFilter2 odd [1, 2, 3]
[3,1]

Hmmm.  So there is a difference.  foldr appears to grab elements from 
the end of the list.  Therefore, to get the same result from the function
that uses foldr, I did this:


myFilter3 pfunc xs = foldr accFunc [] xs
    where accFunc x acc
            | pfunc x       = x : acc
            | otherwise     = acc  


*Main> myFilter3 odd [1, 2, 3]
[1,3]

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 mailing list