What are the outstanding questions in purely functional data structures? 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?
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.