AIOJ

Note

This chapter is optional reading; before reading it, make sure that you have some understanding of functional programming (Functional Programming).

Introduction

A finger tree (Finger Tree) is a purely functional data structure proposed by Ralf Hinze and Ross Paterson.

Why Finger Trees Are Needed

In functional programming, lists are very common data types. For sequence-based operations, including adding and removing elements at both ends (deque operations), inserting, concatenating, and deleting at arbitrary positions, finding an element that satisfies a requirement, and splitting a sequence into subsequences, almost all functional languages provide support. However, these languages have difficulty providing more efficient operations. Even when corresponding implementations exist, they are usually very complex and difficult to use in practice.

Finger trees provide a purely functional sequence data structure that can perform access and operations such as adding to the front or back of a sequence in amortized constant time, as well as concatenation and random access in logarithmic time. In addition to good asymptotic running-time bounds, finger trees are also highly flexible: when combined with monoidal tags on elements (monoidal tag), finger trees can be used to implement efficient random-access sequences, ordered sequences, interval trees, and priority queues.

Basic Structure

Finger trees store data at the tree's "fingers" (leaves), with amortized constant-time access. A finger is a point from which part of a data structure can be accessed. In an imperative language (imperative language), this is called a pointer. In a finger tree, a "finger" refers to a structure pointing to the end of a sequence or a leaf node. A finger tree also stores, at each internal node, the result of applying an associative operation to its descendants. The data stored in internal nodes can be used to provide functionality beyond that of tree-based data structures.

The depth of a finger tree is counted from bottom to top.
The first level of a finger tree, namely the tree's leaf nodes, contains only values and has depth $0$ . The second level has depth $1$ . The third level has depth $2$ , and so on.
The closer to the root, the deeper the subtrees of the original tree (the tree before it became a finger tree) to which the nodes point. Thus, working downward along the tree proceeds from the leaves to the root, which is the opposite of a typical tree data structure. To obtain this structure, we must ensure that the original tree has uniform depth. When declaring node objects, they must be parameterized by the type of their child nodes. Nodes on the spine at depth $1$ and above point to trees; through this parameterization, they can be represented by nested nodes.

Turning a Tree into a Finger Tree

Note

A 2-3 tree is a tree-based data structure in which every node with children (an internal node) has either two children (a $2$ -node) and one data element, or three children (a $3$ -node) and two data elements. A 2-3 tree is a $3$ -order B-tree. Nodes outside the tree (leaf nodes) have no children and contain one or two data elements.

We will begin this process with a balanced 2-3 tree. For a finger tree to work properly, all leaf nodes need to be at the same level. As shown in the figure below (the image is taken from the finger tree paper):

A finger is "a structure that provides efficient access to the nodes of a tree near a particular position." To make a finger tree, we need to place fingers at the left and right ends of the tree, take the leftmost and rightmost internal nodes of the tree, and pull them up so that the rest of the tree hangs between them. This gives us amortized constant-time access to the ends of the sequence.

This new data structure is called a finger tree. A finger tree consists of several layers (the blue boxes below) distributed along its tree spine (the brown line):

data FingerTree a = Empty
                  | Single a
                  | Deep (Digit a) (FingerTree (Node a)) (Digit a)

data Digit a = One a | Two a a | Three a a a | Four a a a a
data Node a = Node2 a a | Node3 a a a

The numbers in the example are nodes containing letters. Each list is divided by the prefix or suffix of each node on the spine. In the transformed 2-3 tree, the digit lists at the top level seem to be able to have lengths of two or three, while those at lower levels have lengths of only one or two. To allow certain applications of finger trees to run so efficiently, finger trees allow from $1$ to $4$ subtrees at each level. The digits of a finger tree can be converted into a list, as follows:

type Digit a = One a | Two a a | Three a a a | Four a a a a

The top level has elements of type $a$ , and the next level has elements of type node $a$ , because of the nodes between the tree spine and the leaves. This generally means that the $n$ th level of the tree has element type $Node^{n}$ $a$ , or a 2-3 tree of depth $n$ . This means that a sequence of $n$ elements is represented by a tree of depth Θ(log n). An element at distance $d$ from the nearest end is stored at depth Θ(log d) in the tree.

Deque Operations

Finger trees can also be used to make efficient double-ended queues. Regardless of whether the structure is persistent, all operations take Θ(1) time. It can be viewed as an extension of the implicit deque¹:

Replacing pairs with 2-3 nodes provides enough flexibility to support efficient concatenation. (To keep deque operations constant-time, Digit must be extended to Four.)
Annotating internal nodes with a monoid allows efficient splitting.

data ImplicitDeque a = Empty
                     | Single a
                     | Deep (Digit a) (ImplicitDeque (a, a)) (Digit a)

data Digit a = One a | Two a a | Three a a a

Time Complexity

Finger trees provide amortized constant-time access to the tree's "fingers" (leaves), where data is stored, as well as logarithmic-time concatenation and splitting in terms of the size of the smaller part. They also store, at each internal node, the result of applying an associative operation to its descendants. The "summary" data stored in internal nodes can be used to provide the functionality of data structures other than trees.

Operation	Finger tree	Annotated 2-3 tree (annotated 2-3 tree)	List (list)	Vector (vector)
`const`,`snoc`	$O(1)$	$O(\log n)$	$O(1)$ / $O(n)$	$O(n)$
`viewl`,`viewr`	$O(1)$	$O(\log n)$	$O(1)$ / $O(n)$	$O(1)$
`measure`/`length`	$O(1)$	$O(1)$	$O(n)$	$O(1)$
`append`	$O(\log \min(l1, l2))$	$O(\log n)$	$O(n)$	$O(m+n)$
`split`	$O(\log \min(n, l-n))$	$O(\log n)$	$O(n)$	$O(1)$
`replicate`	$O(\log n)$	$O(\log n)$	$O(n)$	$O(n)$
`fromList`,`toList`,`reverse`	$O(l)$ / $O(l)$ / $O(l)$	$O(l)$	$O(1)$ / $O(1)$ / $O(n)$	$O(n)$
`index`	$O(\log \min(n, l-n))$	$O(\log n)$	$O(n)$	$O(1)$

Applications

Finger trees can be used to build other trees. For example, a priority queue can be implemented by annotating internal nodes with the minimum priority among the child nodes, while an indexed list/array can be implemented by annotating nodes with the count of leaves among their child nodes. Other applications include random-access sequences (as described below), ordered sequences, and interval trees.

Finger trees can provide average $O(1)$ push, reverse, and pop, and $O(\log n)$ append and split; they can also be adapted to indexed or sorted sequences. Like all functional data structures, they are inherently persistent; that is, old versions of the tree are always retained.

For code implementations, the finite sequence Seq in Haskell's core library is implemented using a 2-3 finger tree (Data.Sequence), and the implementation of the BatFingerTree module in OCaml also uses a general finger tree data structure. Finger trees can be implemented with or without lazy evaluation, but laziness allows a simpler implementation.

References and Further Reading

Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programming 16:2 (2006) pp 197-217.
Finger Tree - Wikipedia

Footnotes

Purely Functional Data Structures, Chris Okasaki (1999) ↩