[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,
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.
More information about the Haskell-Cafe