<p>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.</p>

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

<p>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. </p>

<p>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). </p>

<p>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.</p>

<p>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. </p>

CC BY-SA 2.5
2010-12-31T18:50:45.200Z
what is aliasing in this context ?
Suresh Venkat
CC BY-SA 2.5
2011-01-01T01:29:17.900Z
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.
Neel Krishnaswami
CC BY-SA 2.5
2011-01-04T14:38:47.820Z
"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.
Per Vognsen
CC BY-SA 2.5
2011-01-04T14:45:09.247Z
"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).
Per Vognsen
CC BY-SA 2.5
2010-12-30T17:59:22.570Z
2010-12-30T17:59:22.570Z
Neel Krishnaswami
<blockquote>
  <p>What functional dictionary data structures are important to know about?</p>
</blockquote>

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

<ul>
<li>Patricia trees.</li>
<li>Hash tries.</li>
</ul>

<blockquote>
  <p>What are the pros and cons of these approaches?</p>
</blockquote>

<p>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.</p>

<p>Patricia trees can be several times faster but only permit integer keys.</p>

<p>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.</p>

<p>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.</p>

<p>Similarly, finger trees are not much better in practice.</p>

<blockquote>
  <p>When does it make sense to use a more imperative data structure?</p>
</blockquote>

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

<p>When you need performance (a decent hash table like the .NET <code>Dictionary</code> is typically 10-40&#215; faster than any generic purely functional dictionary).</p>

<p>When you need a weak dictionary because there is no known purely functional weak dictionary.</p>

CC BY-SA 3.0
2012-06-12T11:09:38.657Z
2012-06-12T11:09:38.657Z
J D
<p>I've read a bit about the following data structures:</p>

<ul>
<li>Bagwell's Ideal Hash Tries</li>
<li>Larson's Dynamic hash tables</li>
<li>Red-Black trees</li>
<li>Patricia trees</li>
</ul>

<p>...and I'm sure there are a <em>lot</em> 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:</p>

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

<p>Numbers 2 &amp; 3 are the more important ones though.  :-)</p>

CC BY-SA 2.5
2010-12-29T03:18:03.217Z
Related: [What's new in purely functional data structures since Okasaki?](http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki)  (That question is not restricted to dictionaries.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-29T04:27:09.970Z
This question (other than the item numbered 3) has the feeling of a [big-list].
Kaveh
CC BY-SA 2.5
2010-12-29T14:48:46.197Z
it would be helpful to know whether the above linked question addresses your concerns, and if not why not?
Suresh Venkat
CC BY-SA 2.5
2010-12-30T02:19:07.270Z
@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.
Jason
CC BY-SA 2.5
2010-12-30T17:10:01.303Z
ok. so it might be worth editing the question then.
Suresh Venkat
<ds.data-structures><functional-programming><tree><hash-function>
How do I choose a functional dictionary data structure?
Jason
# How do I choose a functional dictionary data structure?

(Asked by: username_0 on 2010-12-29)

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

**Tags:** ds.data-structures, functional-programming, tree, hash-function

> **Comments:**
> **username_1**: Related: [What's new in purely functional data structures since Okasaki?](http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki)  (That question is not restricted to dictionaries.)  
> **username_2**: This question (other than the item numbered 3) has the feeling of a [big-list].  
> **username_3**: it would be helpful to know whether the above linked question addresses your concerns, and if not why not?  
> **username_0**: @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.  
> **username_3**: ok. so it might be worth editing the question then.  

---

## 2 answers

### Answer by username_4 on 2010-12-30. Score: 16

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.

> **Comments:**
> **username_3**: what is aliasing in this context ?  
> **username_4**: 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.  
> **username_5**: "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.  
> **username_5**: "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).  

---

### Answer by username_6 on 2012-06-12. Score: 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.


---

