[Haskell-beginners] folds -- help!

[Peter Verswyvelen]

Maybe it helps to visualize it like this. Instead of computing the sum by
using a fold with (+), we just construct data:
data Expr = N Int
          | Expr :+: Expr
          deriving Show

ns :: [Expr]
ns = map N [1..3]

lf :: Expr
lf = foldl1 (:+:) ns

rf :: Expr
rf = foldr1 (:+:) ns

For simplicity Iused foldl1 and foldr1, which only work on non-empty lists.

(regarding the weird :+: well in Haskell, you can use operators for data
constructors when they start with a colon)

Run this with GHCi, and evaluate lf and rf. You should get

*Main> lf
(N 1 :+: N 2) :+: N 3
*Main> rf
N 1 :+: (N 2 :+: N 3)

So really, foldl "folds on the left", because the parentheses are on the
left side. Similarly for foldr.

Does this help?

On Mon, Mar 9, 2009 at 5:46 PM, 7stud <bbxx789_05ss at yahoo.com> 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.
>
> 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?
>
>
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090309/add4f687/attachment.htm