[Haskell-cafe] trees and pointers

wren ng thornton wren at freegeek.org
Fri Jul 16 10:05:22 EDT 2010

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=

Live well,

More information about the Haskell-Cafe mailing list