Finger tree

A persistent sequence with amortized constant-time access at both ends, and concatenation and splitting in logarithmic time. The ends are kept in buffers of one to four elements, and the middle is a finger tree of 2-3 nodes, one level deeper at each step down the spine.

The type, and adding at either end.

type 'a node = Node2 of 'a * 'a | Node3 of 'a * 'a * 'a
type 'a digit = One of 'a | Two of 'a * 'a | Three of 'a * 'a * 'a | Four of 'a * 'a * 'a * 'a
 
(* The middle of a Deep holds nodes of 'a: a nested type, one level deeper
   per spine step, so every function over it recurses polymorphically. *)
type 'a t = Empty | Single of 'a | Deep of 'a digit * 'a node t * 'a digit
 
let rec cons : 'a. 'a -> 'a t -> 'a t =
 fun a -> function
  | Empty -> Single a
  | Single b -> Deep (One a, Empty, One b)
  | Deep (One b, m, sf) -> Deep (Two (a, b), m, sf)
  | Deep (Two (b, c), m, sf) -> Deep (Three (a, b, c), m, sf)
  | Deep (Three (b, c, d), m, sf) -> Deep (Four (a, b, c, d), m, sf)
  | Deep (Four (b, c, d, e), m, sf) -> Deep (Two (a, b), cons (Node3 (c, d, e)) m, sf)
 
let rec snoc : 'a. 'a t -> 'a -> 'a t =
 fun t a ->
  match t with
  | Empty -> Single a
  | Single b -> Deep (One b, Empty, One a)
  | Deep (pr, m, One b) -> Deep (pr, m, Two (b, a))
  | Deep (pr, m, Two (b, c)) -> Deep (pr, m, Three (b, c, a))
  | Deep (pr, m, Three (b, c, d)) -> Deep (pr, m, Four (b, c, d, a))
  | Deep (pr, m, Four (b, c, d, e)) -> Deep (pr, snoc m (Node3 (b, c, d)), Two (e, a))
 
let digit_list = function
  | One a -> [ a ] | Two (a, b) -> [ a; b ]
  | Three (a, b, c) -> [ a; b; c ] | Four (a, b, c, d) -> [ a; b; c; d ]
let node_list = function Node2 (a, b) -> [ a; b ] | Node3 (a, b, c) -> [ a; b; c ]
 
let rec to_list : 'a. 'a t -> 'a list = function
  | Empty -> []
  | Single a -> [ a ]
  | Deep (pr, m, sf) ->
      digit_list pr @ List.concat_map node_list (to_list m) @ digit_list sf
 
let rec depth : 'a. 'a t -> int = function
  | Empty | Single _ -> 0
  | Deep (_, m, _) -> 1 + depth m

The middle of a Deep is 'a node t: a finger tree whose elements are nodes of the level above. At depth $d$ an element stands for between $2^{d}$ and $3^{d}$ elements of the sequence, so the spine is logarithmic in the length. Every function over the type calls itself at a different type, which OCaml accepts with an explicit polymorphic annotation, 'a. ....

Building a sequence 1 to 10 from both ends, and the spine depth for sequences built by snoc.

to_list      ->  [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
n =      10   spine depth 2
n =     100   spine depth 4
n =    1000   spine depth 6
n =   10000   spine depth 8
n =  100000   spine depth 10
n = 1000000   spine depth 12

The depth grows by about 2 for each factor of 10, close to $lo g_{3} n$ . cons does constant work unless the front digit is full, in which case it pushes a node of three one level down and leaves a digit of two. Two more conses are then needed before that level can overflow again, and charging each overflow to them gives amortized $O (1)$ per operation, as with a counter in a redundant number system.

Concatenation joins the inner digits of the two trees into nodes and recurses down both spines, in $O (lo g min (n_{1}, n_{2}))$ . Splitting uses a measure: every node carries the monoidal sum of its elements' measures, and a search down the spine finds where a monotone predicate on the running sum changes, in $O (lo g min (i, n - i))$ . With size as the measure this is indexing; with the maximum priority it is a priority queue; with the largest key it is an ordered sequence. Haskell's Data.Sequence is a finger tree measured by size.