[Haskell-cafe] dear traversable
claudiusmaximus at goto10.org
Sat Jul 31 09:29:35 EDT 2010
On 31/07/10 13:49, Stephen Tetley wrote:
> Although I haven't calculated the Big-O scores suspect that original
> post will actually be the best, the solutions that metamorph into a
> list and out again look like they're doing needless extra work.
They're both O(size m) time, and yes the original is best (not least for
its simplicity and elegance); I now think that (on my part) it was a
case of following optimisation strategies without thinking hard enough
whether they apply: ie, traversing only once can be beneficial for space
reasons under certain circumstances 
But as Data.Map is spine-strict, there is no space saving here by
traversing only once, as the spine is already there taking up O(size m)
space before we even start traversing (whereas with lazy lists the spine
might not be taking up any space yet).
 to give a classic example:
mean :: Fractional a => [a] -> a
mean xs = sum xs / genericLength xs
which often consumes O(length xs) space, reducible to O(1) if only one
traversal is performed.
More information about the Haskell-Cafe