Finger tree

Finger tree

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 [ [http://alan.petitepomme.net/cwn/2007.10.30.html#5 Caml Weekly News ] ] which was derived from a proven-correct Coq specification [ [http://www.lri.fr/~sozeau/research/russell/fingertrees.en.html Matthieu Sozeau :: Dependent Finger Trees in Coq ] ] ; and a [http://dnovatchev.spaces.live.com/blog/cns!44B0A32C2CCF7488!582.entry 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 without [citation|last1=Kaplan|first1=H.|last2=Tarjan|first2=R. E.|authorlink2=Robert Tarjan|year=1995|contribution=Persistent lists with catenation via recursive slow-down|title=Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing|pages=93–102.] lazy evaluation, but laziness allows for simpler implementations.

They were first published in 1977 by Leonidas J. Guibas [citation|last1=Guibas|first1=L. J.|authorlink1=Leonidas J. Guibas|last2=McCreight|first2=E. M.|last3=Plass|first3=M. F.|last4=Roberts|first4=J. R.|year=1977|contribution=A new representation for linear lists|title=Conference Record of the Ninth Annual ACM Symposium on Theory of Computing|pages=49–60.] , and periodically refined since (e.g. a version using AVL trees [citation|last=Tsakalidis|first=A. K.|year=1985|title=AVL-trees for localized search|journal=Information and Control|volume=67|pages=173–194.] , non-lazy finger trees, simpler 2-3 finger trees [citation|title=Finger Trees: A Simple General-purpose Data Structure|first1=Ralf|last1=Hinze|first2=Ross|last2=Paterson|journal=Journal of Functional Programming|volume=16|issue=2|year=2006|pages=197–217.] , and so on)

ee also

* Red-black tree

References

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.informatik.uni-bonn.de/~ralf/talks/BCTCS.pdf]
* [http://www.eecs.usma.edu/webs/people/okasaki/pubs.html]
* [http://blogs.msdn.com/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx Example of 2-3 trees in C#]
* [http://dnovatchev.spaces.live.com/blog/cns!44B0A32C2CCF7488!582.entry Example of Hinze/Paterson Finger Trees in C#]
* [http://scala.sygneca.com/code/finger-trees Example of Hinze/Paterson Finger Trees in Scala]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Finger Lakes National Forest — The Finger Lakes National Forest encompasses 16,032 acres (65.9 km²), nestled between Seneca Lake and Cayuga Lake in the Finger Lakes Region of New York State in the United States of America. The forest has over 30 miles (50 km) of… …   Wikipedia

  • finger grass — Crab Crab (kr[a^]b), n. [AS. crabba; akin to D. krab, G. krabbe, krebs, Icel. krabbi, Sw. krabba, Dan. krabbe, and perh. to E. cramp. Cf. {Crawfish}.] 1. (Zo[ o]l.) One of the brachyuran Crustacea. They are mostly marine, and usually have a broad …   The Collaborative International Dictionary of English

  • Tree frog — A tree frog or tree toad is any frog that spends a major portion of its lifespan in an arboreal state. [http://wordnet.princeton.edu/perl/webwn?s=tree%20frog] [http://animals.howstuffworks.com/amphibians/tree frog info.htm] Two lineages of frogs… …   Wikipedia

  • tree frog — any of various arboreal frogs, esp. of the family Hylidae, usually having adhesive disks at the tip of each toe. [1730 40] * * * or tree toad Any of some 550 species (family Hylidae) of mostly arboreal frogs, found worldwide but primarily in the… …   Universalium

  • tree lupine — a shrubby, Californian tree, Lupinus arboreus, of the legume family, having hairy, finger shaped leaflets and fragrant, sulphur yellow flowers. [1880 85] * * * …   Universalium

  • tree lupine — noun evergreen shrub of the Pacific coast of the United States having showy yellow or blue flowers; naturalized in Australia • Syn: ↑Lupinus arboreus • Hypernyms: ↑shrub, ↑bush • Member Holonyms: ↑Lupinus, ↑genus Lupinus …   Useful english dictionary

  • finger cherry — /ˈfɪŋgə tʃɛri/ (say fingguh cheree) noun an Australian tropical tree, Rhodomyrtus macrocarpa, with highly poisonous fruit …  

  • finger lime — noun : a spiny Australian citrus shrub or tree (Microcitrus australasica) with smooth slender elongated fruits …   Useful english dictionary

  • Splay tree — A splay tree is a self balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look up and removal in O(log(n)) amortized time. For many… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”