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.