[Haskell-beginners] folds -- help!

[Daniel Fischer]

Am Montag, 9. März 2009 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.

What they meant was "the value that is the result in case the fold is applied 
to an empty list", in this case the 0, in the definition

fold(l/r) f z xs = ...

the 'z'.

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

Note that in general the list elements and acc have different types, so only 
one of 
accFun acc x
and
accFun x acc
typechecks.

If the types are the same, in general accFun x acc /= accFun acc x, so foldr 
and foldl give different results, too.

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

Since with foldr, the parentheses are grouped to the right:
x0 `f` (x1 `f` (x2 `f` ... (xn `f` z) ... )),

if f can start delivering the result without looking at its second argument, 
you can start consuming the result before the fold has traversed the whole 
list.

Common examples are things like 

concat = foldr (++) [],
so 
concat [l1,l2,l3,l4,l5] = l1 ++ (foldr (++) [] [l2,l3,l4,l5])
and the start (l1) can be used before further reducing the fold,

and = foldr (&&) True

and [True,False,..........]
needs only inspect the list until it encounters the first False (if any, 
otherwise it must of course traverse the whole list)

or = foldr (||) False

foldr is useful if the combination function is lazy in its second argument.

foldl on the other hand can't deliver anything before the whole list is 
consumed. So since foldl builds thunks (except in some easy cases where the 
optimiser sees it should be strict), which would have to be evaluated at the 
end when they've become rather large, foldl isn't as useful and one uses the 
strict left fold, foldl'.