# Persistent data structure: FingerTrees.jl
**URL:** https://discourse.julialang.org/t/persistent-data-structure-fingertrees-jl/138839
**Category:** Package Announcements
**Created:** [August 16, 2026, 7:18am UTC](https://discourse.julialang.org/t/persistent-data-structure-fingertrees-jl/138839 "2026-08-16T07:18:41Z")
**Posts on this page:** 4
**Page:** 1
### Author:  [@mschauer](https://discourse.julialang.org/u/mschauer)
#### Post date: [August 16, 2026, 7:18am UTC](https://discourse.julialang.org/t/persistent-data-structure-fingertrees-jl/138839/1 "2026-08-16T07:18:41Z")
`FingerTrees.jl` ([GitHub - mschauer/FingerTrees.jl: The persistent data structure Finger Tree in Julia · GitHub](https://github.com/mschauer/FingerTrees.jl)) was an old Julia implementation of finger trees, a persistent sequence data structure due to Hinze and Paterson.
Finger trees ([Finger tree - Wikipedia](https://en.wikipedia.org/wiki/Finger_tree)) 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.
```plaintext
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.
---
### Author:  [@mschauer](https://discourse.julialang.org/u/mschauer)
#### Post date: [August 17, 2026, 11:54am UTC](https://discourse.julialang.org/t/persistent-data-structure-fingertrees-jl/138839/2 "2026-08-17T11:54:22Z")
Some more changes removed several remaining compiler and representation costs: trusted internal constructors cut push/build time by roughly two-thirds, specialized pop views reduced end-removal to around 70–80 ns, and iterative indexing became allocation-free at 27 ns. The result is that `FingerTrees.jl` now matches the Rust implementation [fingertrees - Rust](https://docs.rs/fingertrees/latest/fingertrees/) on persistent insertion and construction, while iteration is faster; the remaining gaps are mainly split, concat, and pop.
| operation, (n=32768) | FingerTrees.jl | rust-ft |
| --- | --- | --- |
| push-right | 72 ns | 74 ns |
| build-right | 2.65 ms | 2.46 ms |
| pop-right | 79 ns | 37 ns |
| split-middle | 1.75 μs | 0.71 μs |
| concat | 2.08 μs | 0.83 μs |
| iterate | **113 μs** | 171 μs |
---
### Author:  [@tecosaur](https://discourse.julialang.org/u/tecosaur)
#### Post date: [August 17, 2026, 10:48pm UTC](https://discourse.julialang.org/t/persistent-data-structure-fingertrees-jl/138839/3 "2026-08-17T22:48:42Z")
I can’t day I expect to use this, but I always appreciate a well-implemented data structure. Very nice work!
---
### Author:  [@mschauer](https://discourse.julialang.org/u/mschauer)
#### Post date: [August 18, 2026, 6:17am UTC](https://discourse.julialang.org/t/persistent-data-structure-fingertrees-jl/138839/4 "2026-08-18T06:17:33Z")
lol, same here!