Finger tree

We will start this process with a balanced 2-3 tree. 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.”[1] To make a finger tree we need to put fingers to the right and left ends of the tree and transform it like a zipper. This gives us that constant amortized time access to the ends of a sequence.

To transform, start with the balanced 2-3 tree.

Take the leftmost and rightmost internal nodes of the tree and pull them up so the rest of the tree dangles between them as shown in the image to the right.

Combines the spines to make a standard 2-3 finger tree.

This can be described as:[1]

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

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. In a transformed 2-3 tree it seems that the digit lists at the top level can have a length of two or three with the lower levels only having length of one or two. In order for some application of finger trees to run so efficiently, finger trees allow between one and four subtrees on each level. The digits of the finger tree can be transformed into a list like so:[1]

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

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 ${\displaystyle Node^{n}}$ a, or 2-3 trees of depth n. This means a sequence of n elements is represented by a tree of depth Θ(log n). Even better, an element d places from the nearest end is stored at a depth of Θ(log d) in the tree.[1]

${\displaystyle {\begin{matrix}\mathrm {instance} \ Reduce\ Node\ \mathrm {where} \\\\reducer\ (\prec )\ (Node2\ a\ b)\ z=a\ \prec (b\ \prec \ z)\\reducer\ (\prec )\ (Node3\ a\ b\ c)\ z=a\ \prec (\ b\prec (c\ \prec \ z))\\reducel\ (\succ )\ z\ (Node2\ b\ a)\ =(z\ \succ \ b)\ \succ \ a\\reducel\ (\succ )\ z\ (Node3\ c\ b\ a)\ =((z\ \succ \ c)\succ \ b)\succ \ a\\\\\mathrm {instance} \ Reduce\ FingerTree\ \mathrm {where} \\\\reducer\ (\prec )\ (Empty)\ z\ =z\\reducer\ (\prec )\ (Single\ x)\ z=x\ \prec \ z\\reducer\ (\prec )\ (Deep\ pr\ m\ sf)\ z=pr\ \prec '\ (m\ \prec ''\ (sf\ \prec '\ z))\\where\\(\prec ')\ =reducer\ (\prec )\\(\prec '')\ =reducer\ (reducer\ (\prec ))\\\\reducel\ (\succ )\ z\ (Empty)\ =z\\reducel\ (\succ )\ z\ (Single\ \ x)\ =z\ \succ \ x\\reducel\ (\succ )\ z\ (Deep\ \ pr\ m\ sf)\ =((z\ \succ '\ pr)\ \succ ''\ m)\ \succ '\ sf)\\where\\(\succ ')\ =reducel\ (\succ )\\(\succ '')\ =reducel\ (reducel\ (\succ ))\end{matrix}}}$

Finger trees also make efficient deques. 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.[1]

Finger trees can efficiently implement random-access sequences. This should support fast positional operations including accessing the nth element and splitting a sequence at a certain position. To do this, we annotate the finger tree with sizes.[1]

newtype Size = Size{ getSize :: N }
  deriving (Eq, Ord)

instance Monoid Size where
  ∅ = Size 0
  Size m ⊕ Size n = Size (m + n)

The N is for natural numbers. The new type is needed because the type is the carrier of different monoids. Another new type is still needed for the elements in the sequence, shown below.

newtype Elem a = Elem{ getElem :: a }
newtype Seq a = Seq (FingerTree Size (Elem a))

instance Measured (Elem a) Size where
  ||Elem|| = Size 1

These lines of code show that instance works a base case for measuring the sizes and the elements are of size one. 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.