Finger tree
Encyclopedia
A finger tree is a purely functional
data structure
used in efficiently implementing other functional data structures. A finger tree gives amortized constant time access to the "fingers" (leaves) of the tree, where data is stored, and the internal nodes are labeled in some way as to provide the functionality of the particular data structure being implemented. 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. Finger trees can provide amortized O(1) cons
, reversing, cdr
, O(log n) append and split; and can be adapted to be indexed or ordered sequences.
They have since been used in the Haskell
core libraries (in the implementation of Data.Sequence), and an implementation in OCaml exists which was derived from a proven-correct Coq
specification; and a C# implementation of finger trees was published in 2008; the Yi
text editor
specializes finger trees to finger strings for efficient storage of buffer text. Finger trees can be implemented with or withoutlazy evaluation
, but laziness allows for simpler implementations.
They were first published in 1977 by Leonidas J. Guibas
, and periodically refined since (e.g. a version using AVL trees, non-lazy finger trees, simpler 2-3 finger trees, and so on)
Purely functional
Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...
data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
used in efficiently implementing other functional data structures. A finger tree gives amortized constant time access to the "fingers" (leaves) of the tree, where data is stored, and the internal nodes are labeled in some way as to provide the functionality of the particular data structure being implemented. For example, a priority queue
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
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. Finger trees can provide amortized O(1) cons
Cons
In computer programming, cons is a fundamental function in most dialects of the Lisp programming language. cons constructs memory objects which hold two values or pointers to values. These objects are referred to as cells, conses, non-atomic s-expressions , or pairs...
, reversing, cdr
Car and cdr
car and cdr are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.Thus, the expression evaluates to x, and evaluates to...
, O(log n) append and split; and can be adapted to be indexed or ordered sequences.
They have since been used in the Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
core libraries (in the implementation of Data.Sequence), and an implementation in OCaml exists which was derived from a proven-correct Coq
Coq
In computer science, Coq is an interactive theorem prover. It allows the expression of mathematical assertions, mechanically checks proofs of these assertions, helps to find formal proofs, and extracts a certified program from the constructive proof of its formal specification...
specification; and a C# implementation of finger trees was published in 2008; the Yi
Yi (editor)
Yi is a text editor written and extensible in Haskell. The goal of Yi is to provide a flexible, powerful and correct editor core dynamically scriptable in Haskell....
text editor
Text editor
A text editor is a type of program used for editing plain text files.Text editors are often provided with operating systems or software development packages, and can be used to change configuration files and programming language source code....
specializes finger trees to finger strings for efficient storage of buffer text. Finger trees can be implemented with or withoutlazy evaluation
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
, but laziness allows for simpler implementations.
They were first published in 1977 by Leonidas J. Guibas
Leonidas J. Guibas
Leonidas John Guibas is a professor of computer science at Stanford University, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories. Guibas was a student of Donald Knuth at Stanford, where he received his Ph.D. in 1976...
, and periodically refined since (e.g. a version using AVL trees, non-lazy finger trees, simpler 2-3 finger trees, and so on)
External links
- http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
- http://hackage.haskell.org/packages/archive/EdisonCore/1.2.1.1/doc/html/Data-Edison-Concrete-FingerTree.html
- http://www.eecs.usma.edu/webs/people/okasaki/pubs.html
- Example of 2-3 trees in C#
- Example of Hinze/Paterson Finger Trees in Java
- Example of Hinze/Paterson Finger Trees in C#
- Example of Hinze/Paterson Finger Trees in Scala
- http://www.dougalstanton.net/blog/index.php/2008/12/12/a-brief-look-at-fingertrees/
- "Fingertrees and Monoids"
- "Finger tree library for Clojure"