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

  • 2
    $\begingroup$ Please clarify if you mean appending an element or appending two vectors, and whether you're interested in purely functional data structures or its OK to use mutable state. Also, should access be O(1) to the latest version of the structure, or to all versions? Worst case or amortized? $\endgroup$
    – jkff
    Dec 14, 2014 at 2:28
  • $\begingroup$ Amortized would be fine. I meant appending two vectors ("concatenation"). Mutable state is fine as long as all the operations on the objects are referentially transparent: i.e. users should be able to pretend that they are purely functional vectors. This kinda implies O(1) to all versions, the idea of "version" is not exposed to the user. $\endgroup$
    – ithisa
    Dec 14, 2014 at 3:34
  • $\begingroup$ I think you'd get what you want (O(1) indexing, O(log n) concat, very fast element append) by combining Clojure's HAMT with some generic techniques along the lines of Haskell's "diff arrays" hackage.haskell.org/package/array-… - e.g. make the pointer block be a slice of a (mutably growable, COW) array. On append, append to the array and return a grown slice. On append to a non-recent slice, you'll need to create a new mutable block, but it solves the typical "append in a loop" problem. $\endgroup$
    – jkff
    Dec 14, 2014 at 5:39
  • $\begingroup$ Hmm. That seems interesting. So with such a technique, constructing an array by (prepend 1 (prepend 2 (prepend 3 (prepend 4 empty)))) would be reasonably fast? $\endgroup$
    – ithisa
    Dec 14, 2014 at 14:38
  • 1
    $\begingroup$ Yes, Hinze and Paterson's finger trees have amortized $O(1)$ car, amrtized $O(\log n)$ updating, and amortized $O(\log n)$ append. $\endgroup$
    – jbapple
    Dec 17, 2014 at 14:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy