FingerTrees.jl (GitHub - mschauer/FingerTrees.jl: The persistent data structure Finger Tree in Julia · GitHub) was an old Julia implementation of finger trees, a persistent sequence data structure due to Hinze and Paterson.
Finger trees (Finger tree - Wikipedia) are interesting because they combine efficient access at both ends with logarithmic splitting and search, and unusually cheap concatenation. They are a good fit for functional data structures where old versions remain usable after an update.
The package was originally written for a much earlier Julia 0.7 and then abandoned. At the time, there was an awkward trade-off: representing the recursive structure precisely in the type system could lead to excessive compilation, while hiding that structure behind abstract types made compilation manageable but gave the compiler much less information at runtime, and surprisingly poor performance for operations that should be cheap.
Today we first modernized the package without changing its algorithms without much trouble for the coding agent, then progressively replaced abstract recursive fields by closed unions describing the actual finite possibilities.
For example, a finger tree is not an arbitrary subtype of FingerTree; internally it is one of EmptyFT, SingleFT, or DeepFT. Digits have widths one through four, and 2–3-tree nodes likewise come from a small closed family.
Making those alternatives explicit had an immediate effect. Julia’s inference could follow the recursive structure much further, and allocations dropped substantially.
We also replaced those open tuple return boundaries by small concrete result types, in particular for the split algorithm and gave the rebuilding helpers closed return contracts.
FingerTree comparison
assoc 0.36 μs PV: 0.09 μs
concat 3.1 μs PV: 406 μs
iterate 126 μs PV: 264 μs
split-middle 5.0 μs Vector: 9.6 μs
FingerTrees.jl runs now in Julia 1.14 and is over two orders of magnitude faster than concatenating the persistent vectors in this benchmark, while allocating vastly less memory, whereas persistent vector is as expected better for random indexing and repeated right-end updates.
PS: I revisited this because of the announcement that Julia will support mutually recursive data structures, but that wasn’t really needed to get this working.