2018-03-03 09:35:28 +00:00
|
|
|
|
---
|
|
|
|
|
|
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'
|
2018-06-08 12:05:27 +00:00
|
|
|
|
year: 2006
|
2018-03-03 09:35:28 +00:00
|
|
|
|
|
|
|
|
|
|
---
|
|
|
|
|
|
# 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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
([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.
|
