10
$\begingroup$

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. :-)

$\endgroup$
  • $\begingroup$ Related: What's new in purely functional data structures since Okasaki? (That question is not restricted to dictionaries.) $\endgroup$ – Tsuyoshi Ito Dec 29 '10 at 3:18
  • $\begingroup$ This question (other than the item numbered 3) has the feeling of a [big-list]. $\endgroup$ – Kaveh Dec 29 '10 at 4:27
  • 2
    $\begingroup$ it would be helpful to know whether the above linked question addresses your concerns, and if not why not? $\endgroup$ – Suresh Venkat Dec 29 '10 at 14:48
  • $\begingroup$ @Suresh - That answers #1, but 2 and 3 were the more important ones. I'm mostly looking for a big-picture overview so I can determine which ones are worth studying in more depth. $\endgroup$ – Jason Dec 30 '10 at 2:19
  • 2
    $\begingroup$ ok. so it might be worth editing the question then. $\endgroup$ – Suresh Venkat Dec 30 '10 at 17:10
16
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ what is aliasing in this context ? $\endgroup$ – Suresh Venkat Dec 31 '10 at 18:50
  • 6
    $\begingroup$ Aliasing is when you have multiple references to the same piece of data. If that data is mutable, then reasoning about a program that uses it has to explicitly take into account all the other subprograms that may access and modify it. If that piece of data is immutable, then you can reason locally about a program that uses it, ignoring aliasing, since you know no one who can access the data can modify it. $\endgroup$ – Neel Krishnaswami Jan 1 '11 at 1:29
  • $\begingroup$ "but implementing deletion in an imperative red-black tree with parent pointers will leave you contemplating suicide" Check out Sedgewick's left-leaning red-black trees. The general case of deletion is reduced to delete-min by a standard trick, and delete-min itself is very simple for LLRB trees. No parent pointers needed. $\endgroup$ – Per Vognsen Jan 4 '11 at 14:38
  • 1
    $\begingroup$ "This is generally pretty horrible, full of bugs, and prone to losing the performance advantage of the imperative algorithm." Norman Ramsey's paper on using zippers for control flow graphs in an optimizing compiler provides an example of a compelling compromise. You effectively have a local heap for supporting easy and efficient in-place rewiring of references between basic blocks in a CFG, but the manipulation of the contents of basic blocks is functional (or semi-functional, depending on your philosophical view of zippers). $\endgroup$ – Per Vognsen Jan 4 '11 at 14:45
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.