Benchmarking Zippers in Haskell

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.

data Tree
  = Atom !Int !String
  | Object !Int !(Map String Tree)
  deriving (Show, Eq, Generic, NFData)

access :: [String] -> (Tree -> Tree) -> Tree -> Tree
access [] f t = f t
access (k : ks) f (Object vers ts) = Object vers $ Map.alter modifyChild k ts
 where
  modifyChild Nothing = error "Invalid path to access"
  modifyChild (Just child) = Just $ access ks f child
access _ _ _ = error "Invalid path to access"

Then we implement the zipper data structure and its operations for traversing and modifying the tree.

data Zipper = Zipper
  { focus :: !Tree
  , breadcrumbs :: [Crumb]
  }
  deriving (Show, Eq, Generic, NFData)

type Move = Zipper -> Zipper

data Crumb = Crumb
  { holeKey :: !String
  , storedVers :: !Int
  , siblings :: !(Map String Tree)
  }
  deriving (Show, Eq, Generic, NFData)

goDown :: String -> Zipper -> Zipper
goDown k (Zipper (Object vers ts) bs)
  | (Just child, siblings') <- Map.updateLookupWithKey (\_ _ -> Nothing) k ts =
      Zipper child (Crumb k vers siblings' : bs)
goDown k (Zipper f _) = error $ "Cannot go to child '" ++ k ++ "' of tree: " ++ show f

goUp :: Zipper -> Zipper
goUp (Zipper t (Crumb key vers siblings' : bs)) = Zipper (Object vers (Map.insert key t siblings')) bs
goUp (Zipper _ []) = error "Already at the top"

Benchmark Design

Each benchmark performs 100,000 operations. Three full trees are generated with the following shapes:

Here, depth counts edges from the root. All three trees have exactly 1,048,576 leaves, but their shapes differ.

The workloads are:

1. 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.
2. Random edit. Generate paths in the same way, then increment the node's integer. Both Atom and Object are updated.
3. 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: a/b (random start) -> a/b/c/d (down two) -> a/b (up two from a leaf) -> root (up two) -> x/y/z (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 ghc -O2.

Trees, paths, and relative zipper moves are generated and fully evaluated outside the timed region. Update benchmarks
use whnf: the strict tree fields and Data.Map.Strict 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 Tree.

The commands are:

cabal run zippers-time

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.

Analysis of the Results

A root-based lookup performs one Map.lookup 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, especially reads; for such workloads, a zipper is usually not worth the overhead.
• For a batch of nearby edits, keep the zipper open between edits and convert it back to a complete tree only after the batch.

The complete benchmark source is available in
the repository.

Further Reading

• Vít Šefl, Performance Analysis of Zippers, 2019.