52
$\begingroup$

This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998.

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – J D Jan 30 '11 at 23:43
19
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ One candidate for fully persistent (but not confluently persistent) arrays is presented in Confluently Persistent Tries for Efficient Version Control. 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. $\endgroup$ – jbapple Sep 23 '10 at 13:25
  • 1
    $\begingroup$ 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. $\endgroup$ – jbapple Sep 26 '10 at 21:39
12
$\begingroup$

What other purely functional data structure problems are open?

Here's one:

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

Improve this answer
$\endgroup$
8
  • 6
    $\begingroup$ Okay, I'll bite. What's a weak hash table? $\endgroup$ – Jeffε Jun 11 '12 at 15:28
  • 4
    $\begingroup$ It's a hash table that allows its elements to be garbage collected if only it (and other weak maps) contain references to it. $\endgroup$ – Havvy Jun 12 '12 at 0:54
  • 3
    $\begingroup$ @JɛffE 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). $\endgroup$ – J D Jun 12 '12 at 9:20
  • 3
    $\begingroup$ @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. $\endgroup$ – Neel Krishnaswami Jun 15 '12 at 13:44
  • 6
    $\begingroup$ @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 wiki.ecmascript.org/doku.php?id=harmony:weak_maps for an example. $\endgroup$ – Sam Tobin-Hochstadt Jun 19 '12 at 15:50

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.