How do I choose a functional dictionary data structure? I've read a bit about the following data structures:


Bagwell's Ideal Hash Tries
Larson's Dynamic hash tables
Red-Black trees
Patricia trees


...and I'm sure there are a lot of others out there.  I've seen very little in the way of what each one is better suited for, or why I would choose one over another.  So, here are a few questions along these lines:


What functional dictionary data structures are important to know about?
What are the pros and cons of these approaches?
When does it make sense to use a more imperative data structure?


Numbers 2 &amp; 3 are the more important ones though.  :-)
I can't really answer #2 without getting lost (there are too many dimensions along which you can compare these structures), but for #3 the answer is pretty simple.

Use an imperative data structure if: (a) there is absolutely no aliasing, or (b) you really need to use aliasing for efficient broadcast. 

If there is no aliasing of your data structure at all, then you are not taking advantage of the fact that functional data structures are persistent. So there is no reason to pay for their cost. There are two caveats to this advice. First, you may prefer the simplicity of implementation of a functional data structure: implementing deletion for a functional red-black tree will make you curse, but implementing deletion in an imperative red-black tree with parent pointers will leave you contemplating suicide. Second, assignment can be more expensive than you expect in a gc'd language, since writes can get data structures moved out of the young generation. We really don't have a good theory of cache effects and gc, so you have no choice but to do benchmarking. 

Second, if you need a broadcast channel, then a shared data structure is an excellent way to do it. With a constant-time update, you can tell arbitrarily many other people that a value has changed. (This is why union-find is such a great data structure.) With a purely functional setup, either you need to modify all those other people, or give them abstract pointers into a state you code up manually (which is a kind of obtuse thing to do). 

If you either don't want to reason about aliasing and object ownership, or if you need multiple versions of the same data structure (you need both a new and an old version, say), then just use a functional data structure.

The place where I find following this advice the hardest is with graph algorithms. There are lots of really elegant imperative graph algorithms, but it's often the case (say, when writing compilers) that you also want persistence. People typically try to split the difference and use the cool imperative algorithm but try to bolt versioning onto the side to get persistence. This is generally pretty horrible, full of bugs, and prone to losing the performance advantage of the imperative algorithm.