[Haskell-cafe] dear traversable

[Stephen Tetley]

On 31 July 2010 12:13, wren ng thornton <wren at freegeek.org> wrote:

> Well, that's one traversal of the original map, but you have to traverse the
> new maps repeatedly with all those M.insert calls. And since Data.Map is a
> balanced tree, that could lead to a whole lot of work rebalancing things.


Thanks. Indeed, I was missing that the traversal is cheap compared to
the rebuilding.

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.