<blockquote>
  <p>What other purely functional data structure problems are open?</p>
</blockquote>

<p>Here's one:</p>

<p>What is the purely functional equivalent of a weak hash table?</p>

CC BY-SA 3.0
2012-06-11T15:28:34.767Z
Okay, I'll bite.  What's a weak hash table?
Jeffε
CC BY-SA 3.0
2012-06-12T00:54:13.930Z
It's a hash table that allows its elements to be garbage collected if only it (and other weak maps) contain references to it.
Havvy
CC BY-SA 3.0
2012-06-12T09:20:17.530Z
@JɛﬀE I'm anticipating your next question "why would anyone want a weak hash table?". A graph can be represented as a set of vertices (e.g. a hash set) and a map from vertices to vertices (e.g. a hash table). If your graph evolves over time such that subgraphs become unreachable then it is useful to have the garbage collector reclaim those unreachable subgraphs for you. Weak hash tables do this. In the absence of a purely functional weak dictionary you're looking at either leaking memory or writing your own purely functional garbage collector (which will be unfeasibly invasive).
J D
CC BY-SA 3.0
2012-06-15T13:44:53.650Z
@JonHarrop: it's easy to prove that a pure version of a weak reference is impossible, since weak references make the language's semantics nondeterministic and purely functional languages are deterministic. If you additionally mark the nondeterminism in the type then the usual implementation works. You need dependent types (to prove that an implementation gives the same answers regardless of the contents of the reference) if you want to safely mask the effect.
Neel Krishnaswami
CC BY-SA 3.0
2012-06-15T15:21:04.510Z
@NeelKrishnaswami "weak references make the language's semantics nondeterministic". You mean dereferencing a weak reference will return a value or null depending upon whether or not the GC has collected the reference? True but isn't the idea to collect unreachable subgraphs that, by definition, cannot be reached so the user would never be able to dereference a weak reference, only search for a key in a weak dictionary that must still be there if they still have the key?
J D
CC BY-SA 3.0
2012-06-15T15:22:07.347Z
Someone else pointed out that purity means no physical hashing or equality, only structurally. If you can create structurally identical keys at will then they can never be collected...
J D
CC BY-SA 3.0
2012-06-16T05:40:35.923Z
@JonHarrop: Weak data structures can be used to create nondeterminism. Your (correct) argument is that this particular program doesn't expose that nondetermism, but that fact depends on the correctness proof of this particular program. Since a compiler doesn't have that proof, it can't know that the whole program (the graph algorithm) is deterministic, even though locally it isn't (there are uses of weak refs). This is why I mentioned dependent types: they let you supply the compiler that missing proof.
Neel Krishnaswami
CC BY-SA 3.0
2012-06-19T15:50:09.450Z
@NeelKrishnaswami, I don't think that's the case.  You can create weak data structures that don't create non-determinism, such as a weak table that doesn't support enumeration (or counting).  See http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps for an example.
Sam Tobin-Hochstadt
CC BY-SA 3.0
2011-01-30T23:41:08.667Z
2012-06-11T14:48:06.437Z
2012-06-11T14:48:06.437Z
J D
<p>I'll interpret the question somewhat liberally. For Okasaki-style data structures, memoization is a form of implicit mutation that has a side effect on running time. Thus I'll take the question to concern persistent data structures in the strict sense rather than data structures with a purely functional implementation, which are a subset of the former. By strict I mean that you should able to access older versions of a data structure without penalty, the tree of versions can branch arbitrarily, etc.</p>

<p>In that context, I consider persistent UNION-FIND an important open problem. There's the Conchon-Filliâtre paper that was mentioned in the other thread. A commenter already brought up an issue with their so-called persistent array: it's really only semi-persistent. But suppose you replace it with a hash trie or some other truly persistent array that behaves better in the worst (and arguably average) case but worse in the best case. That still leaves an important issue open:</p>

<p>The paper gives a formal proof of correctness in Coq. But they fail to address the amortized complexity either formally or informally. It's very much <em>not</em> clear to me that the complicated behind-the-scenes mutation results in the expected amortized complexity in all cases. When I last thought about it, I felt somewhat confident I could construct a counterexample if I put effort into it. Even if I'm wrong about that last part, the lack of a proper analysis is a major gap; it's clear that Trajan's classical amortization analysis of UNION-FIND doesn't directly transfer.</p>

CC BY-SA 2.5
2010-09-23T13:25:47.437Z
One candidate for fully persistent (but not confluently persistent) arrays is presented in [Confluently Persistent Tries for Efficient Version Control](http://erikdemaine.org/papers/ConfluentTries_Algorithmica/). The authors claim O(lg lg n) slowdown, beating Dietz et al's O(lg lg m) slowdown, where m is the number of operations that have been performed on the array.
jbapple
CC BY-SA 2.5
2010-09-26T21:39:38.923Z
I'll also add that, though Okasaki's lazy amortized structures are often much simpler than the alternatives, I don't know of any data structure that can be implemented that way that can't also be implemented (with the same time bounds, but worst-case) in a truly purely functional way.
jbapple
CC BY-SA 2.5
2010-09-23T03:37:11.317Z
2010-09-23T03:49:59.187Z
2010-09-23T03:49:59.187Z
Per Vognsen
<p>This question is inspired by <a href="https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki">another question about what's new in PFDS since the publication of Okasaki's book in 1998</a>.</p>

<p>I'll start with two questions I have:</p>

<ul>
<li>Is there a purely functional set data structure that approaches the speed of hash tables? Tries aren't  there yet.</li>
<li>Are there purely functional finger trees with O(1) append? The best so far is O(lg lg n), devised by Kaplan and Tarjan.</li>
</ul>

<p>What other purely functional data structure problems are open?</p>

CC BY-SA 2.5
2011-01-30T23:43:58.163Z
I take it you mean tries as in hash trees rather than the more general dictionaries with keys that are sequences? FWIW, I think it is impossible to approach the good old hash table here.
J D
<big-list><ds.data-structures><functional-programming>
What are the outstanding questions in purely functional data structures?
jbapple
# What are the outstanding questions in purely functional data structures?

(Asked by: username_0 on 2010-09-22)

This question is inspired by [another question about what's new in PFDS since the publication of Okasaki's book in 1998](https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki).

I'll start with two questions I have:

* Is there a purely functional set data structure that approaches the speed of hash tables? Tries aren't there yet.
* Are there purely functional finger trees with O(1) append? The best so far is O(lg lg n), devised by Kaplan and Tarjan.

What other purely functional data structure problems are open?

**Tags:** big-list, ds.data-structures, functional-programming

> **Comments:**
> **username_1**: I take it you mean tries as in hash trees rather than the more general dictionaries with keys that are sequences? FWIW, I think it is impossible to approach the good old hash table here.  

---

## 2 answers

### Answer by username_6 on 2010-09-23. Score: 20 | Accepted answer

I'll interpret the question somewhat liberally. For Okasaki-style data structures, memoization is a form of implicit mutation that has a side effect on running time. Thus I'll take the question to concern persistent data structures in the strict sense rather than data structures with a purely functional implementation, which are a subset of the former. By strict I mean that you should able to access older versions of a data structure without penalty, the tree of versions can branch arbitrarily, etc.

In that context, I consider persistent UNION-FIND an important open problem. There's the Conchon-Filliâtre paper that was mentioned in the other thread. A commenter already brought up an issue with their so-called persistent array: it's really only semi-persistent. But suppose you replace it with a hash trie or some other truly persistent array that behaves better in the worst (and arguably average) case but worse in the best case. That still leaves an important issue open:

The paper gives a formal proof of correctness in Coq. But they fail to address the amortized complexity either formally or informally. It's very much *not* clear to me that the complicated behind-the-scenes mutation results in the expected amortized complexity in all cases. When I last thought about it, I felt somewhat confident I could construct a counterexample if I put effort into it. Even if I'm wrong about that last part, the lack of a proper analysis is a major gap; it's clear that Trajan's classical amortization analysis of UNION-FIND doesn't directly transfer.

> **Comments:**
> **username_0**: One candidate for fully persistent (but not confluently persistent) arrays is presented in [Confluently Persistent Tries for Efficient Version Control](http://erikdemaine.org/papers/ConfluentTries_Algorithmica/). The authors claim O(lg lg n) slowdown, beating Dietz et al's O(lg lg m) slowdown, where m is the number of operations that have been performed on the array.  
> **username_0**: I'll also add that, though Okasaki's lazy amortized structures are often much simpler than the alternatives, I don't know of any data structure that can be implemented that way that can't also be implemented (with the same time bounds, but worst-case) in a truly purely functional way.  

---

### Answer by username_1 on 2011-01-30. Score: 13

> What other purely functional data structure problems are open?

Here's one:

What is the purely functional equivalent of a weak hash table?

> **Comments:**
> **username_2**: Okay, I'll bite.  What's a weak hash table?  
> **username_3**: It's a hash table that allows its elements to be garbage collected if only it (and other weak maps) contain references to it.  
> **username_1**: @JɛﬀE I'm anticipating your next question "why would anyone want a weak hash table?". A graph can be represented as a set of vertices (e.g. a hash set) and a map from vertices to vertices (e.g. a hash table). If your graph evolves over time such that subgraphs become unreachable then it is useful to have the garbage collector reclaim those unreachable subgraphs for you. Weak hash tables do this. In the absence of a purely functional weak dictionary you're looking at either leaking memory or writing your own purely functional garbage collector (which will be unfeasibly invasive).  
> **username_4**: @JonHarrop: it's easy to prove that a pure version of a weak reference is impossible, since weak references make the language's semantics nondeterministic and purely functional languages are deterministic. If you additionally mark the nondeterminism in the type then the usual implementation works. You need dependent types (to prove that an implementation gives the same answers regardless of the contents of the reference) if you want to safely mask the effect.  
> **username_1**: @NeelKrishnaswami "weak references make the language's semantics nondeterministic". You mean dereferencing a weak reference will return a value or null depending upon whether or not the GC has collected the reference? True but isn't the idea to collect unreachable subgraphs that, by definition, cannot be reached so the user would never be able to dereference a weak reference, only search for a key in a weak dictionary that must still be there if they still have the key?  
> **username_1**: Someone else pointed out that purity means no physical hashing or equality, only structurally. If you can create structurally identical keys at will then they can never be collected...  
> **username_4**: @JonHarrop: Weak data structures can be used to create nondeterminism. Your (correct) argument is that this particular program doesn't expose that nondetermism, but that fact depends on the correctness proof of this particular program. Since a compiler doesn't have that proof, it can't know that the whole program (the graph algorithm) is deterministic, even though locally it isn't (there are uses of weak refs). This is why I mentioned dependent types: they let you supply the compiler that missing proof.  
> **username_5**: @NeelKrishnaswami, I don't think that's the case.  You can create weak data structures that don't create non-determinism, such as a weak table that doesn't support enumeration (or counting).  See http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps for an example.  

---

