Re: [Haskell-cafe] dear traversable

On 31 July 2010 12:13, wren ng thornton 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.