Meetup summary

2024-11-01 - 2-3 Finger Trees (part 1)

Recommended reading:

• The paper that introduced 2-3 Finger Trees (open access) and its accompanying web page.
• Andrew Gibiansky’s blog post, which describes a concrete implementation of some of the operations in practical detail.
• Koen Claessen’s YouTube presentation of a finger tree functional pearl. This is essentially a pared down 2-3 finger tree supporting just a subset of the operations in the original paper. However, it gives good motivation and background for the design and some discussion of performance characteristics which were left out in the original paper.
• The original finger tree paper. This is only tangentially related to what we’ll discuss, as the original data structure was not purely applicative, but it provides some interesting historical context.

Agenda:

• Introduce 2-3 Finger Trees, a purely applicative data structure with very appealing properties even when used in a fully persistent setting.
• Discuss the origins and motivation of 2-3 Finger Trees.
• Describe the core data structure and invariants.
• “Implement” the basic finger tree operations live on the whitepoard.