Jan-Willem Maessen wrote:
As you observe, it's really down to constant factors. The reason IntMap (or any digital trie) is so interesting is that it is simple enough that the constant factors are quite good---in particular we don't waste a lot of time figuring out if we're going to need to rearrange the tree structure on the fly. That turns out to amortize quite a few extra level traversals in a lot of settings.
This simplicity of not rebalancing also allows for more sharing in a persistent setting, which can be a big gain for programs with the right kinds of data distributions.
It also offers really elegant implementations of union and unions. Whether that means they're quickish I leave to the benchmarkers.
In my experience (NLP work), the performance of unions for tries is one of their major selling points. In Okasaki's venerable benchmarks[1], they vastly outperform all competitors for merging. Even in imperative-land, that's one of the reasons tries are so common in NLP and are often chosen over hashmaps for certain tasks. [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452 -- Live well, ~wren