Finger tree
In computer science, a finger tree is a purely functional data structure that can be used to efficiently implement other functional data structures.
A finger tree gives amortized constant time access to the "fingers" (leaves) of the tree, which is where data is stored, and concatenation and splitting logarithmic time in the size of the smaller piece.
It also stores in each internal node the result of applying some associative operation to its descendants.
Ralf Hinze and Ross Paterson state a finger tree is a functional representation of persistent sequences that can access the ends in amortized constant time.
Concatenation and splitting can be done in logarithmic time in the size of the smaller piece.
The structure can also be made into a general purpose data structure by defining the split operation in a general form, allowing it to act as a sequence, priority queue, search tree, or priority search queue, among other varieties of abstract data types.
[1] A finger is a point where one can access part of a data structure; in imperative languages, this is called a pointer.
In the images shown below, the fingers are the lines reaching out of the spine to the nodes.
A finger tree is composed of different layers which can be identified by the nodes along its spine.
Each of those nodes has a link to the next level of the spine until they reach the root.
To get this nice and unusual structure, we have to make sure the original tree has a uniform depth.
To ensure that the depth is uniform, when declaring the node object, it must be parameterized by the type of the child.
For the finger tree to work, all the leaf nodes need to also be level.
A finger is "a structure providing efficient access to nodes of a tree near a distinguished location.
This gives us that constant amortized time access to the ends of a sequence.
Combines the spines to make a standard 2–3 finger tree.
This can be described as:[1] The digits in the examples shown are the nodes with letters.
Each list is divided by the prefix or suffix of each node on the spine.
The digits of the finger tree can be transformed into a list like so:[1] And so on the image, the top level has elements of type a, the next has elements of type Node a because the node in between the spine and leaves, and this would go on meaning in general that the nth level of the tree has elements of type
Even better, an element d places from the nearest end is stored at a depth of Θ(log d) in the tree.
Whether the structure is persistent or not, all operations take Θ(1) amortized time.
The analysis can be compared to Okasaki's implicit deques, the only difference being that the FingerTree type stores Nodes instead of pairs.
[4] For example, a priority queue can be implemented by labeling the internal nodes by the minimum priority of its children in the tree, or an indexed list/array can be implemented with a labeling of nodes by the count of the leaves in their children.
[1] Finger trees can provide amortized O(1) pushing, reversing, popping, O(log n) append and split; and can be adapted to be indexed or ordered sequences.
And like all functional data structures, it is inherently persistent; that is, older versions of the tree are always preserved.
Finger trees can efficiently implement random-access sequences.
Another new type is still needed for the elements in the sequence, shown below.
The use of newtypes doesn't cause a run-time penalty in Haskell because in a library, the Size and Elem types would be hidden from the user with wrapper functions.
With these changes, the length of a sequence can now be computed in constant time.
[8] There is also a verified implementation in Isabelle (proof assistant) from which programs in Haskell and other (functional) languages can be generated.
