How do I choose a functional dictionary data structure?

Question

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:

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

Numbers 2 & 3 are the more important ones though. :-)

Answer 1

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.

Answer 2

What functional dictionary data structures are important to know about?

Height-balanced binary trees and tries of them are a good all-round compromise. Also:

• Patricia trees.
• Hash tries.

What are the pros and cons of these approaches?

Height-balanced binary trees and tries of them are a good all-round compromise for atomic keys. Tries are the same for keys that are sequences, e.g. string keys.

Patricia trees can be several times faster but only permit integer keys.

Hash tries can be several times faster than balanced binary trees, particularly if hashing is cheaper than comparison and polymorphism has an overhead (e.g. strings on .NET) and writing pointers into the heap is fast (e.g. VMs like the JVM and CLR that have been optimized for imperative languages rather than functional languages). Hash tries also permit the internal use of mutation as an optimization.

Red-black trees are less important because they do not have any significant benefits over height-balanced trees but have the significant disadvantage that they do not permit efficient union, intersection and difference.

Similarly, finger trees are not much better in practice.

When does it make sense to use a more imperative data structure?

When your dictionary is populated once and then used only for lookups, i.e. frozen.

When you need performance (a decent hash table like the .NET Dictionary is typically 10-40× faster than any generic purely functional dictionary).

When you need a weak dictionary because there is no known purely functional weak dictionary.