[Haskell-cafe] Reasoning about performance

[Scott Pakin]

On 09/03/2013 06:09 PM, Dan Burton wrote:
> Here's a fun alternative for you to benchmark, using an old trick. I kind of doubt that this one will optimize as nicely as the others, but I am by no means an optimization guru:
>
> allPairsS :: [a] -> [(a, a)]
> allPairsS xs = go xs [] where
>    go [] = id
>    go (y:ys) = (map (\a -> (y, a)) ys ++) . go xs

Ummm...it loops forever.  Oh wait; I see it now: The final token
should be "ys", not "xs".  With this modification the code
unfortunately uses both a lot of time and a lot of memory.  For
reference, here was my original, naive version (using what we now know
to be a flawed way to measure execution time in a non-strict
language):

     Prelude Control.DeepSeq AllPairs> deepseq (allPairs1 [1..10000]) True
     True
     (4.85 secs, 4004173984 bytes)

And here's the resource usage of the difference-list implementation:

     Prelude Control.DeepSeq AllPairs> deepseq (allPairs4 [1..10000]) True
     True
     (11.34 secs, 8404906432 bytes)

> Further reading:
> http://www.haskell.org/haskellwiki/Difference_list

Thanks for the pointer.  I don't see why it's called a "difference
list", but I get the basic idea.

-- Scott