[Haskell-cafe] dear traversable

[Claude Heiland-Allen]

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 [1]

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


[1] 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.


Claude
-- 
http://claudiusmaximus.goto10.org