[Haskell-cafe] [newbie] processing large logs

Antti-Juhani Kaijanaho antti-juhani at kaijanaho.fi
Sun May 14 07:13:36 EDT 2006


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?

They're complementary.

If the result is of a type where partial evaluation is possible (say, a 
list: between "not evaluated" and "fully evaluated", there are as many 
intermediate stages of evaluation as there are elements in the list), 
then foldr is the better choice, as it constructs the output list (or 
whatever) lazily.  (You also need to make sure that the fold parameter 
function is lazy in the "rest of output" parameter.)

If the result is of a type that doesn't allow partial evaluation (an 
integer, for example: there is no intermediate stage between "not 
evaluated" and "fully evaluated"), or used in a context where laziness 
is not a virtue, then it pays to avoid laziness in its evaluation: hence 
foldl' is the better choice. (You also need to make sure that the fold 
parameter function is strict in the accumulator parameter.)

In elementary (nth-language) Haskell, one is generally trying to learn 
the stuff about Haskell that is *different* from conventional languages, 
so in elementary tutorials the rule of thumb "foldr is better" works. 
It's just one of the half-lies that people get told in elementary 
courses that one needs to augment in later stages of learning :)


More information about the Haskell-Cafe mailing list