[Haskell-cafe] trees and pointers

[wren ng thornton]

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