---
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.