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: 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 uniform