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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
