Finger tree
From Wikipedia, the free encyclopedia
A finger tree is a purely functional data structure used in efficiently implementing other functional data structures, such as strings. A finger tree gives amortized constant time access to the "fingers" of the tree, which are usually the ends; 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 O'Caml exists[1] which was derived from a proven-correct Coq specification[2]; the Yi text editor specializes finger trees to finger strings for efficient storage of buffer text. Finger trees can be implemented with or without[3]lazy evaluation, but laziness allows for simpler implementations.
They were first published in 1977 by Leo Guibas[4], and periodically refined since (e.g. a version using AVL trees[5], non-lazy finger trees, simpler 2-3 finger trees[6], and so on)
[edit] See also
[edit] References
- ^ Caml Weekly News
- ^ Matthieu Sozeau :: Dependent Finger Trees in Coq
- ^ Kaplan, H. and 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. and 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:173-194
- ^ "Finger Trees: A Simple General-purpose Data Structure", Ralf Hinze and Ross Paterson. in [[Journal of Functional Programming 16:2 (2006), pages 197-217
