Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?

Question

Context: For fun and perhaps for actual use, I'm making my own programming language that would compile to Typed Racket, a statically-typed Lisp dialect. One of the major features I want to implement is rampantly persistent data structures in the standard library. Persistent dictionaries are basically a solved problem (AVL trees, red-black trees aren't much slower than hash tables), I'm now trying to find a good solution for persistent vectors.

In Okasaki's famous Purely Functional Data Structures, "skew binary random access lists" were introduced. Apparently, they have $O(1)$ prepend, $O(1)$ index to first and last, and $O(\log n)$ random access and update. By my own little microbenchmarks, this data structure is one of the fastest ways to implement a persistent vector: in particular it seems to be much faster than hash-trie based methods like the one used by Clojure, or things such as Braun trees. In fact, indexing near the beginning is only around 2x slower than Lisp linked lists' car operation! In addition, prepend and modification near the front is extremely fast, which allows these lists to be used in places where linked lists are idiomatic (implementing map by recursion on the remaining portion for example). Clojure's hash tries, to put it vulgarly, suck really bad when appended to in a loop due to copying a 32-pointer block over and over, and thus Clojure also uses a primitive linked-list data type. I want to avoid that.

In the same book, "catenable lists" that have $O(\log n)$ append were discussed, but these lists have $O(n)$ performance on update and index.

Bagwell and Rompf's RRB-Trees: Efficient Immutable Vectors gives a modification to the Clojure-style persistent hash trie that allows $O(\log n)$ append (and surprisingly, range) while preserving $O(\log n)$ indexing. However, I'm not that keen to adopt a hash-trie for my standard persistent vector, since that would mean giving up the incredibly fast performance of skewed binary random access lists. Hash-tries are fine for implementing dictionaries, but I feel that they would be too slow for a general array/list datatype.

Is there a data structure with $O(1)$ car and $O(\log n)$ updating, like Okasaki's skewed binary random access lists, while having sublinear append?

Edit: Herp derp, skewed binary RA lists don't have $O(1)$ access to the middle

Answer 1

You can achieve the exact characteristics you're looking for with Finger Trees. The most basic finger tree is defined in terms of 2-3 tree nodes:

data Tree23 a = Node2 a a | Node3 a a a
data Affix a = One a | Two a a | Three a a a | Four a a a a

data FingerTree a = Empty 
                  | Leaf a
                  | Trunk {
                      left :: Affix a
                      trunk :: FingerTree (Tree23 a)
                      right :: Affix a
  
                  }

A full implementation (the one I based this answer on) can be found at this blog post. In order to achieve the O(lg n) indexing, simply augment the structure so that each node knows exactly how many leaf nodes are under it, and use that to examine only O(lg n) nodes to find the right element. (It's the same way that character offsets are computed into rope data structures, incidentally.)