74 lines
2.6 KiB
Markdown
74 lines
2.6 KiB
Markdown
---
|
||
created_at: '2016-12-27T13:36:08.000Z'
|
||
title: 'Finger Trees: A Simple General-Purpose Data Structure (2006)'
|
||
url: http://www.staff.city.ac.uk/~ross/papers/FingerTree.html
|
||
author: tosh
|
||
points: 267
|
||
story_text:
|
||
comment_text:
|
||
num_comments: 75
|
||
story_id:
|
||
story_title:
|
||
story_url:
|
||
parent_id:
|
||
created_at_i: 1482845768
|
||
_tags:
|
||
- story
|
||
- author_tosh
|
||
- story_13263038
|
||
objectID: '13263038'
|
||
year: 2006
|
||
|
||
---
|
||
# Finger Trees: A Simple General-purpose Data Structure
|
||
|
||
[Ralf Hinze](http://www.cs.ox.ac.uk/ralf.hinze/) and [Ross
|
||
Paterson](http://www.soi.city.ac.uk/%7Eross/), [*Journal of Functional
|
||
Programming*](http://journals.cambridge.org/action/displayJournal?jid=JFP)
|
||
16(2):197–217, 2006.
|
||
doi:[10.1017/S0956796805005769](https://doi.org/10.1017/S0956796805005769)
|
||
|
||
## Summary
|
||
|
||
We present 2-3 finger trees, a functional representation of persistent
|
||
sequences supporting access to the ends in amortized constant time, and
|
||
concatenation and splitting in time logarithmic in the size of the
|
||
smaller piece. Representations achieving these bounds have appeared
|
||
previously, but 2-3 finger trees are much simpler, as are the operations
|
||
on them. Further, by defining the split operation in a general form, we
|
||
obtain a general purpose data structure that can serve as a sequence,
|
||
priority queue, search tree, priority search queue and more.
|
||
|
||
The basic structure is expressed as a non-regular (or nested) type:
|
||
|
||
data FingerTree a = Empty
|
||
| Single a
|
||
| Deep (Digit a) (FingerTree (Node a)) (Digit a)
|
||
|
||
data Digit a = One a | Two a a | Three a a a | Four a a a a
|
||
data Node a = Node2 a a | Node3 a a a
|
||
|
||
This produces trees of 2-3 trees, with favoured access (fingers) at the
|
||
ends, like
|
||
|
||
![](FingerTree/example-tree.svg)
|
||
|
||
([more examples](FingerTree/more-trees.html)) and also supports
|
||
efficient concatenation. To support splitting and searching, we annotate
|
||
the internal nodes of the tree with values drawn from an
|
||
application-specific monoid.
|
||
|
||
- [PDF](FingerTree.pdf), [gzipped
|
||
PostScript](FingerTree/FingerTree.ps.gz),
|
||
[BibTeX](FingerTree/FingerTree.bib).
|
||
- A sequence implementation based on the application discussed in
|
||
section 4.2 is included as a module
|
||
[Data.Sequence](http://hackage.haskell.org/package/containers/docs/Data-Sequence.html)
|
||
in the Glasgow Haskell Compiler and other Haskell implementations.
|
||
Note: The class `Reduce` in the paper is replaced by the class
|
||
[Foldable](http://hackage.haskell.org/package/base/docs/Data-Foldable.html).
|
||
- The [fingertree
|
||
package](http://hackage.haskell.org/package/fingertree) is a generic
|
||
finger tree structure, for use as a base for various container
|
||
types.
|