[Haskell-cafe] [newbie] processing large logs

[Udo Stenzel]

Eugene Crosser wrote:
> Having read "Yet another Haskell tutorial" (note on p.20), doesn't foldl
> have to read the complete list before it can start processing it
> (beginning from the last element)?  As opposed to foldr that can fetch
> elements one by one as they are needed?

Both foldl and foldr start from the left of the list; dictated by the
structure of the list datatype nothing else is possible.  The actual
difference is that foldl passes an accumulator along and returns the
final value of the accumulator.  This also means that foldl is tail
recursive and foldr isn't.

Depending on what you want to do, both combinators can start processing
right away.  foldr does so only if the folded function is lazy in its
second argument (the list constructor is an example of such a function,
but Map.insert isn't), foldl' always does so.  You cannot get a result
from foldl' before the complete input is consumed.

If it's still unclear, you should take the definitions of foldr, foldl
and foldl' and simulate their reductions by hand on paper.  You should
see how foldr cannot apply a strict function (like (+)) before the
complete(!) list is transformed into a gargantuan thunk, how foldl just
plain refuses to apply the obviously needed reduction step and cannot be
persuaded to do so and how foldl' is what you want.  You'll also see how
everything is different for a lazy funktion (like (:)).


Udo.
-- 
It is easier to get forgiveness than permission.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060514/367c09e0/attachment.bin