On 09/03/2013 05:43 PM, Bob Ippolito wrote:
Haskell's non-strict evaluation can often lead to unexpected results when doing tail recursion if you're used to strict functional programming languages. In order to get the desired behavior you will need to force the accumulator (with something like Data.List's foldl', $!, seq, BangPatterns, etc.).
I had previously tried BangPatterns and recall it not making any difference. However, this result now makes sense given what you described in terms of tail recursion thwarting some of the benefits of non-strict evaluation.
I think what's happening with allPairs2 is that GHC is throwing away the the list during the traversal since the result of the computation isn't used at all. I get very different timings (still fast, but no longer orders of magnitude difference) for allPairs2 if the result is still around. You could probably figure this out with the heap profiler.
h> deepseq (allPairs2 [1..10000]) True True (2.47 secs, 4403724176 bytes) h> let x = allPairs2 [1..10000] (0.00 secs, 510488 bytes) h> deepseq x True True (10.47 secs, 4401625192 bytes) h> deepseq x True True (2.21 secs, 1031864 bytes)
Ah, I hadn't thought about that. Even though deepseq is forcing the complete evaluation, it can discard evaluated results (and maybe even deforest) in the lazy allPairs1 and allPairs2 implementations but not in the tail-recursive-but-not-lazy allPairs3. Using your let trick to prevent the result from being discarded cases caused my memory subsystem to scream in pain in all three cases. I had to reduce the problem size quite a bit and still ended up spending hours of real time in GC. With this approach, allPairs1 and allPairs2 take an equal amount of time and roughly equal amounts of memory. allPairs3 takes twice as long and uses a bit more than half the memory: Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs1 [1..4000] (0.00 secs, 512968 bytes) Prelude Control.DeepSeq System.Mem AllPairs> performGC (1.31 secs, 1113528 bytes) Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True True (0.74 secs, 641687568 bytes) Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs2 [1..4000] (0.00 secs, 510144 bytes) Prelude Control.DeepSeq System.Mem AllPairs> performGC (3.53 secs, 848312 bytes) Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True True (0.74 secs, 705185688 bytes) Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs3 [1..4000] (0.01 secs, 510072 bytes) Prelude Control.DeepSeq System.Mem AllPairs> performGC (27.00 secs, 956096 bytes) Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True True (1.54 secs, 385915160 bytes) Thanks for the explanation, -- Scott