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 also stores in each internal node the result of applying some associative operation to its descendants. This "summary" data stored in the internal nodes can be used to provide the functionality of data structures other than trees. 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) 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.
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.
- Caml Weekly News
- Matthieu Sozeau :: Dependent Finger Trees in Coq
- Kaplan, H.; Tarjan, R. E. (1995), "Persistent lists with catenation via recursive slow-down", Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pp. 93–102.
- Guibas, L. J.; McCreight, E. M.; Plass, M. F.; Roberts, J. R. (1977), "A new representation for linear lists", Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, pp. 49–60.
- Tsakalidis, A. K. (1985), "AVL-trees for localized search", Information and Control 67 (1-3): 173–194, doi:10.1016/S0019-9958(85)80034-6.
- Hinze, Ralf; Paterson, Ross (2006), "Finger Trees: A Simple General-purpose Data Structure" (PDF), Journal of Functional Programming 16 (2): 197–217, doi:10.1017/S0956796805005769.
- Example of 2-3 trees in C#
- Example of Hinze/Paterson Finger Trees in Java
- Example of Hinze/Paterson Finger Trees in C#
- "Monoids and Finger Trees in Haskell"
- "Finger tree library for Clojure"
- "Finger tree in Scalaz"
- "Verified Finger Trees in Isabelle/HOL"
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|