Finger Trees

6.12

top ← prev up next →

Finger Trees

Finger trees are a general purpose data structure that can be used to implement many other data structures including multiple variations of sequences, deques, and queues. Finger trees support amortized constant time access to both ends as well as logarithmic time concatenation and splitting.

Finger trees achieve the log append and split bounds by caching a "measurement" in each node. the actual measurement computed is determined by the specific data structure being represented. For example, caching the size of the subtree at each node implements a random-access sequence.

Based on Hinze and Paterson’s JFP 2006 [HP06] paper.

This implementation currently does not utilize laziness, because preliminary benchmarking indicates that it is not beneficial to do so. In other words, the benefits of laziness do not outweigh the practical overhead that laziness incurs. Thus, the theoretical bounds from the Hinze and Paterson’s paper may not hold when the data structures are used persistently. However, the data structures should still perform well in practice.

1 Finger Trees

(require ftree)

package: ftree

procedure
(mk-ftree ∅ elem-sz ⊕) → ftree?
  ∅ : any/c
  elem-sz : (-> any/c any/c)
  ⊕ : (-> any/c any/c any/c)

Creates an empty finger tree. ∅ is the "measurement" of the empty tree. elem-sz takes an element in the tree and returns the measurement for that element. Finally, ⊕ must be an associative binary operation that combines measurements.

procedure
(ftree? x) → boolean?
x : any/c

Returns #t if x is an finger tree and #f otherwise.

procedure
(ft-empty? ft) → boolean?
ft : ftree?

Indicates whether the given finger tree is empty.

value
empty-ft : ftree?

The empty finger tree.

procedure
(ft-consL x ft) → ftree?
x : any/c
ft : ftree?

Inserts the given value in the finger tree on the left.

procedure
(ft-hdL ft) → any/c
ft : ftree?

Returns the leftmost element from the finger tree. Errors on an empty tree.

procedure
(ft-tlL ft) → ftree?
ft : ftree?

Returns the given finger tree without its leftmost element. Errors on an empty tree.

procedure
(ft-hd+tlL ft) →
any/c ftree?
ft : ftree?

Combination of ft-hdL and ft-tlL, for efficiency.

procedure
(ft-consR x ft) → ftree?
x : any/c
ft : ftree?

Inserts the given value in the finger tree on the right.

procedure
(ft-hdR ft) → any/c
ft : ftree?

Returns the rightmost element from the finger tree. Errors on an empty tree.

procedure
(ft-tlR ft) → ftree?
ft : ftree?

Returns the given finger tree without its rightmost element. Errors on an empty tree.

procedure
(ft-hd+tlR ft) →
any/c ftree?
ft : ftree?

Combination of ft-hdR and ft-tlR, for efficiency.

procedure
(ft-append ft1 ft2) → ftree?
ft1 : ftree?
ft2 : ftree?

Appends the given finger trees.

procedure
(ft-split p? ft) →
ftree? ftree?
p? : (-> any/c boolean?)
ft : ftree?

Splits the given finger tree into two parts such that the given predicate is false for all elements in the first part and true for all elements in the second part.

value
gen:ft : any/c

A generic interface (see Generic Interfaces) for finger tree-based data structures. Any data structure that implements this interface may use the operations above.

gen:mk : (-> any/c any/c (-> any/c any/c) any/c any/c any/c) : Builds a new finger tree based on an existing finger tree. Takes five arguments: existing-ftree ∅ sz-fn ⊕ internal-ftree.

2 Random-Access Sequences

(require raseq)

procedure
(raseq? x) → boolean?
x : any/c

Identifies random-access sequences.

procedure
(mk-raseq) → raseq?

Makes an empty random access sequence.

value
empty-ras : raseq?

An empty random access sequence.

procedure
(ra-empty? ras) → boolean?
ras : raseq?

Indicates whether the given random-access sequence is empty.

procedure
(ra-splitat i ras) →
raseq? raseq?
i : exact-nonnegative-integer?
ras : raseq?

Splits the given random-access sequence at the given index.

procedure
(ra-ref ras i) → any/c
ras : raseq?
i : exact-nonnegative-integer?

Returns the ith element of the given random-access sequence.

3 Priority Queues

(require pqueue)

procedure
(pqueue? x) → boolean?
x : any/c

Identifies priority queues.

procedure
(mk-pqueue <=) → pqueue?
<= : (-> any/c any/c boolean?)

Makes an empty priority queue using the given comparison function.

procedure
(pq-empty? pq) → boolean?
pq : pqueue?

Indicates whether the given priority queue is empty.

procedure
(pq-top pq) → any/c
pq : pqueue?

Returns the top element in the priority queue.

procedure
(pq-rest pq) → pqueue?
pq : pqueue?

Returns a new priority queue that is the given queue but with the topmost element removed.

procedure
(pq-top+rest pq) →
any/c pqueue?
pq : pqueue?

Combination of pq-top and pq-rest, for efficiency.

4 Ordered Sequences

(require orderedseq)

From Hinze and Paterson’s paper: "ordered sequences [can be seen as an optimization] of, and subsume, priority queues, as we have immediate access to the smallest and the greatest element, and search trees, as we can partition ordered sequences in logarithmic time."

Differences with pqueues:

Ordered sequences store elements in sorted order, so the ft-hd and ft-tl functions can grab both min and max elements in constant time, but inserting elements requires a special os-insert function.
Priority queues store elements in arbitrary order, using the "measure" function, ie sz, to determine the order, so ft-cons can be used to insert.

procedure
(oseq? x) → boolean?
x : any/c

Identifies an ordered sequence.

procedure
(mk-oseq <) → oseq?
< : (-> any/c any/c boolean?)

Makes an empty ordered sequence using the given comparison function. NOTE: The given comparison function must not include equality because when partitioning, the implementation assumes that the equality elements are in the right partition. So < is ok but <= will not work. The equal? function is used for equality.

procedure
(os-empty? os) → boolean?
os : oseq?

Indicates whether the given ordered sequence is empty.

procedure
(os-partition x os) →
oseq? oseq?
x : any/c
os : oseq?

Partitions the given ordered sequence into two parts such that all elements in the first part are "less than" the given x with respect to the previously specified comparison, and all elements in the second part are "greater than or equal to" x.

procedure
(os-insert x os) → oseq?
x : any/c
os : oseq?

Inserts x into os, maintaining proper order.

procedure
(os-delete-all x os) → oseq?
x : any/c
os : oseq?

Returns a new ordered sequence with all x’s deleted.

procedure
(os-top os) → any/c
os : oseq?

Returns the top element of the ordered sequence.

procedure
(os-remove-top os) → oseq?
os : oseq?

Returns the given oredered sequence without the top element.

procedure
(os-bot os) → any/c
os : oseq?

Returns the bottom element of the ordered sequence.

procedure
(os-remove-bot os) → oseq?
os : oseq?

Returns the given oredered sequence without the bottom element.

procedure
(os-merge os1 os2) → oseq?
os1 : oseq?
os2 : oseq?

Merges the given ordered sequences, maintaining proper order.

5 Interval Trees

(require intervaltree)

Represents sets of intervals where an interval is a pair of real numbers, lo and hi, with lo <= hi. Intervals are sorted in ascending order of the lo’s, when added via it-insert (but not with any of the ft-cons functions). The cached measure is an interval where the lo is the lo of the rightmost element and the hi is the maximum of the element hi’s.

procedure
(itree? x) → boolean?
x : any/c

Identifies an interval tree.

procedure
(mk-itree) → itree?

Makes an empty interval tree.

procedure
(it-empty? it) → boolean?
it : itree?

Identifies an empty interval tree.

procedure
(it-insert lo hi it) → itree?
  lo : number?
  hi : number?
  it : itree?

Inserts the specified interval in the given interval tree, maintaining ordering.

procedure
(it-search it lo hi) → (or/c interval? #f)
  it : itree?
  lo : number?
  hi : number?

Of the intervals in the given interval tree that intersect the given interval, returns the one with the lowest lo.

procedure
(it-match it lo hi) → (listof interval?)
  it : itree?
  lo : number?
  hi : number?

Returns all intervals in the given interval tree that intersect the given interval.

procedure
(interval? x) → boolean?
x : any/c

Identifies an interval struct.

procedure
(interval lo hi) → interval?
lo : number?
hi : number?

Constructs an interval struct.

procedure
(interval-low i) → number?
i : interval?

Returns the interval lo.

procedure
(interval-high i) → number?
i : interval?

Returns the interval hi.

procedure
(interval-intersect? i j) → boolean?
i : interval?
j : interval?

Indicates if interval i and j intersect, where intersection means (<= (interval-low i) (interval-high j)) and (<= (interval-low j) (interval-high i)) is true.

Bibliography

[HP06]

Ralf Hinze and Ross Paterson, “Finger trees: a simple general-purpose data structure,” Journal of Functional Programming, 2006.

top ← prev up next →

1	Finger Trees
2	Random-Access Sequences
3	Priority Queues
4	Ordered Sequences
5	Interval Trees
	Bibliography