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 :)

Udo Stenzel wrote:

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.

I think that I get it now. foldl will actually yield any result when it hits the end of the list, while foldr will give you partial result (if partial result makes any sense, that is) after each iteration. And to get any advantage of the latter, you need to be able to consume that "partial result" element-by-element. Right? Anyway, I understand that you used 'seq' in your example as a way to "strictify" the function that updates accumulator. Could you (or anyone) explain (in plain English, preferably:) the reason why 'seq' is the way it is. In the first place, why does it have the first argument at all, and what should you put there? Eugene P.S. just FYI: after the changes, my benchmark program stops growing with the growth of data set, and in compiled form it has the same RAM footprint as the equivalent (interpreted) perl script. Still, it consumes 20 times more CPU... P.P.S. Thanks people, you are really helpful!

Eugene Crosser wrote:

Anyway, I understand that you used 'seq' in your example as a way to "strictify" the function that updates accumulator. Could you (or anyone) explain (in plain English, preferably:) the reason why 'seq' is the way it is. In the first place, why does it have the first argument at all

If you write 'seq a b' it means: "Should you need to evaluate b, evaluate (the top constructor of) a first." The example at hand was something like update' key value map = let value' = lookupWithDefault 0 key map in value' `seq` insert key value' map We assume that your program will somehow demand the final value of the map involved, so the 'insert ...' expression will be evaluated at some point. Due to lazy semantics that doesn't mean that value' is evaluated, instead an unevaluated thunk is put into the map to be evaluated once you look it up. Since it is this thunk which takes up all the space, we have to make sure it is evaluated eagerly. That's what the 'seq' does: if evaluation of the map is demanded, value' has to be evaluated before. Notice that there is an application of seq inside of foldl', too. Foldl would build an expression like this: ( insert kn vn ( ... ( insert k2 v2 ( insert k1 v1 empty ) ) ... ) ) Nothing demands the evaluation of the deeply nested part. Foldl' places seq at the appropriate places, so evaluation progresses from the inside out, which is exactly what you need. If you mistakenly used foldl, the 'seq' in the update function would never be triggered. (A single forgotten 'seq' can sometimes ruin everything. This makes "sprinkling seqs until it works" quite frustrating.)

and what should you put there?

I wish I had a good rule of thumb here. Accumulators are a good candidate, the things deep in data structures are good, too, and heap profiling might point you at the right place.

Still, it consumes 20 times more CPU...

Well, that's probably the result of strings being represented as linked lists of unicode characters and Data.Map not being tailored to structured keys. You can make your code faster if you don't care that it gets uglier. Udo. -- If you're not making waves, you're not underway - Adm. Nimitz

martine:

On 5/14/06, Eugene Crosser wrote:

...

main = printMax . (foldr processLine empty) . lines =<< getContents [snip] The thing kinda works on small data sets, but if you feed it with 250,000 lines (1000 distinct), the process size grows to 200 Mb, and on 500,000 lines I get "*** Exception: stack overflow" (using runhaskell from ghc 6.2.4).

To elaborate on Udo's point: If you look at the definition of foldr you'll see where the stack overflow is coming from: foldr recurses all the way down to the end of the list, so your stack gets 250k (or attempts 500k) entries deep so it can process the last line in the file first, then unwinds.

Also, don't use runhaskell! Compile the code with -O :) -- Don