In the previous post, we explored zippers and their applications in functional programming.
In this post, we benchmark their performance against a root-based approach.
Two Approaches We define a simple tree data structure and the naive root-based approach for traversing and modifying the tree.
Then we implement the zipper data structure and its operations for traversing and modifying the tree.
Benchmark Design Each benchmark performs 100,000 operations.
Three full trees are generated with the following shapes: Depth × width nodes Children per Map 5 × 16 1,118,481 16 10 × 4 1,398,101 4 20 × 2 2,097,151 2 Here, depth counts edges from the root.
All three trees have exactly 1,048,576 leaves, but their shapes differ.
The workloads are: Random lookup.
Choose a path by selecting its depth uniformly from 1 through the maximum depth, then selecting each key uniformly.
Add the node’s integer to a checksum.
Random edit.
Generate paths in the same way, then increment the node's integer.
Both and are updated.
Local edit.
Start by editing a node at a random path.
Before each following edit, move one or two levels up or down.
At a leaf, the next move must be up; after editing the root, restart at another random path.
For example: (random start) -> (down two) -> (up two from a leaf) -> (up two) -> (random restart).
Measurement Details These results are based on running the benchmarks on a MacBook Air M4 with 24 GB of RAM, using the following environment: arm64, macOS 26.3.1 GHC 9.10.3, Cabal 3.12.1.0 Criterion 1.6.5.0 containers 0.7, random 1.3.1 fixed seed 20260716 The test program is compiled with .
Trees, paths, and relative zipper moves are generated and fully evaluated outside the timed region.
Update benchmarks use : the strict tree fields and force each update, without adding an unrelated traversal of the entire result.
The zipper is returned to the root at the end of each batch, so both update implementations produce the same .
The commands are: Timing Results Each time is Criterion’s mean for the entire 100,000-operation batch.
Values are shown as root-based time / zipper time — faster implementation and speedup.
The speedup is the slower time divided by the faster time; for example, root 3.86× means the zipper took 3.86 times as long as the root-based implementation.
Tree Random lookup Random edit Local edit 5 × 16 21.97 / 84.89 ms — root 3.86× 53.41 / 90.09 ms — root 1.69× 32.17 / 31.52 ms — roughly tied 10 × 4 20.96 / 84.93 ms — root 4.05× 56.86 / 87.92 ms — root 1.55× 26.18 / 16.61 ms — zipper 1.58× 20 × 2 33.76 / 114.34 ms — root 3.39× 88.20 / 118.11 ms — root 1.34× 30.45 / 9.14 ms — zipper 3.33× Analysis of the Results A root-based lookup performs one at each level and allocates very little.
The zipper has to update the map and allocate memory whenever it moves down, so it is slower for random lookups.
Random edits narrow the gap because the root-based implementation must also rebuild every map on the path.
The zipper is still slower because it travels farther than the root-based implementation: it usually needs to climb close to the root before moving to the next target.
The path between two random targets is usually longer than the path from the root to either target.
For the local workload, the root-based implementation starts over for every edit even though consecutive paths share most of their prefix.
On the deepest tree, the root-based implementation still traverses a long path for each edit, while the zipper moves only about 1.5 edges between nearby targets.
The root-based implementation is also much faster on local edits than on random edits.
This likely reflects better CPU-cache locality because consecutive operations revisit the same branches.
The increasing advantage is not caused by depth in isolation: these test shapes become narrower as they become deeper.
Smaller maps make per-level operations cheaper for both implementations.
Practical Takeaway Use the root-based approach for isolated or scattered operations, e