7.1 Introduction to fingertrees

Fingertrees are a generalised form of deque, that we can parameterise to compute a value, called the “measure” of a fingertree. This measure will be updated incrementally as we add and remove elements from the fingertree. Among other things, this allows fingertrees to be used where you otherwise might have written a custom data structure.

To compute the measure, fingertrees require pieces of information: a converter, a combiner, and an identity.

• The converter is a procedure of one argument, that maps values in the fingertree to other values which are used for computing the measure.
• The combiner is a procedure of two arguments, and combines these into one value representing them both. A combiner must be associative i.e.

  (combine A (combine B C)) ≡ (combine (combine A B) C)
  

  for all values A, B and C.

• An identity is a value that represents the measure of an empty fingertree. It must obey the rule that (combine X identity), (combine identity X) and X are always the same.

To make things more concrete, a simple use of a fingertree is as a deque that keeps a running total. In this case, the converter can simply be the function (lambda (x) x) if it is a deque of integers, the combiner would be +, and the identity 0.

(define l '(3 1 4 1 5 9))

(define ft (list->fingertree l 0 + (lambda (x) x)))

(fingertree-measure ft)
⇒ 23

(fingertree-measure (fingertree-snoc ft 2))
⇒ 25

(let-values (((head tail) (fingertree-uncons ft)))
  (fingertree-measure tail))
⇒ 20

Mathematically speaking, the return type of the converter, the combiner and the identity element are expected to form a monoid.

This document describes version 0.5.0-devel.1 of MMCK PFDS.