Manlio Perillo wrote:
By the way, about insertWith/alter; from IntMap documentation:
insertWithKey: O(min(n,W) alter: O(log n)
So, alter is more efficient than insertWithKey? And what is that `W` ?
As Claus says it's the maximum (value of Int; number of keys). It's in an easily overlooked comment at the top of the IntMap page, last I checked. As for which is faster, it depends. The O(min(n,W)) stuff is effectively linear because n can't exceed W (what would you use for the key?), but it's a smart linear that rivals O(log n). Because the values of n are so small, what really matters here are the constant factors not the asymptotic complexity. Also it depends a lot on what operations you really need. If you're interested in the details, I highly recommend Okasaki&Gill's paper[1] where they introduce IntMap. It's eminently readable and gives comparative numbers to other datastructures for all the basic operations. [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452 -- Live well, ~wren