<p>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:</p>
<pre><code>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
  
                  }
</code></pre>
<p>A full implementation (the one I based this answer on) can be found at <a href="https://andrew.gibiansky.com/blog/haskell/finger-trees/" rel="nofollow noreferrer">this blog post.</a> In order to achieve the <code>O(lg n)</code> 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.)</p>

CC BY-SA 4.0
2023-03-14T22:01:46.870Z
2023-03-14T22:01:46.870Z
Glenn Tang
<p>Context: For fun and perhaps for actual use, I'm making my own programming language that would compile to <a href="http://docs.racket-lang.org/ts-guide/" rel="noreferrer">Typed Racket</a>, 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.</p>

<p>In Okasaki's famous <em>Purely Functional Data Structures</em>, "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' <code>car</code> 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 <code>map</code> by recursion on the remaining portion for example). Clojure's hash tries, to put it vulgarly, suck <em>really</em> 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.</p>

<p>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.</p>

<p>Bagwell and Rompf's <em>RRB-Trees: Efficient Immutable Vectors</em> 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.</p>

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

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

CC BY-SA 3.0
2014-12-14T02:28:35.483Z
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?
jkff
CC BY-SA 3.0
2014-12-14T03:34:28.137Z
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.
ithisa
CC BY-SA 3.0
2014-12-14T05:39:35.243Z
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" http://hackage.haskell.org/package/array-0.2.0.0/docs/Data-Array-Diff.html - 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.
jkff
CC BY-SA 3.0
2014-12-14T14:38:53.777Z
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?
ithisa
CC BY-SA 3.0
2014-12-14T15:17:50.000Z
I'm not so sure about prepend, but it would be fast for append.
jkff
CC BY-SA 3.0
2014-12-15T16:59:41.993Z
I am just scrtaching the back of my skull, but where do finger trees stand on this issue?
Andrej Bauer
CC BY-SA 3.0
2014-12-17T14:53:16.717Z
Yes, Hinze and Paterson's finger trees have amortized $O(1)$ `car`, amrtized $O(\log n)$ updating, and amortized $O(\log n)$ append.
jbapple
<ds.data-structures><functional-programming>
Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?
ithisa
# Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?

(Asked by: username_0 on 2014-12-13)

Context: For fun and perhaps for actual use, I'm making my own programming language that would compile to [Typed Racket](http://docs.racket-lang.org/ts-guide/), 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

**Tags:** ds.data-structures, functional-programming
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_1**: 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" http://hackage.haskell.org/package/array-0.2.0.0/docs/Data-Array-Diff.html - 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.  
> **username_0**: 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?  
> **username_1**: I'm not so sure about prepend, but it would be fast for append.  
> **username_2**: I am just scrtaching the back of my skull, but where do finger trees stand on this issue?  
> **username_3**: Yes, Hinze and Paterson's finger trees have amortized $O(1)$ `car`, amrtized $O(\log n)$ updating, and amortized $O(\log n)$ append.  

---

## 1 answers

### Answer by username_4 on 2023-03-14. Score: 3

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.)


---

