This note about zippers follows Backtracking Iterators (Jean-Christophe Filliâtre). The paper has examples in OCaml but they translate to Haskell fairly directly. Literate Haskell source for this post is here: https://github.com/carlohamalainen/playground/tree/master/haskell/zipper. To run this file, first install QuickCheck:

cabal update
cabal install QuickCheck


A tree datatype

For our examples, we use a simple algebraic datatype, a balanced binary tree with integer labels for the nodes:

Here is an example tree:

We would normally draw this tree like this, with E for Empty:

      2
/ \
/   \
1     3
/ \   / \
E   E E   4
/ \
E   E


Think about traversing the tree. At the beginning there is no path - we are at the top of the tree. Otherwise we have gone down the left subtree or the right subtree.

If we went down the left branch at a node, we would have at hand the path that we followed to get to this node, the value at the node (an integer), and the tree on the right subtree that we did not visit.

Start at the top of the tree:

path: Top (haven't gone anywhere)

tree:
2
/ \
/   \
1     3
/ \   / \
E   E E   4
/ \
E   E


Now walk down the left branch.

path: went left, have a 2, and the subtree
to the right of us is
3
/ \
E   4
/ \
E   E

we are focused on this subtree:

1
/ \
E   E



Encode this information in a type:

A zipper is a tree with a path.

Working with zippers

The initial zipper is just the tree with no path.

Conversely, if we have a zipper and we are at the top, we can get the tree out of it.

Intuitively, we would expect that unZipper . createZipper = id, and we can check this using QuickCheck. First, provide an instance of Arbitrary for our binary trees:

Now the property unZipper . createZipper = id can be written as:

Check it:

*Zipper> quickCheck prop_finish_create
+++ OK, passed 100 tests.


Looks good. Use verboseCheck prop_finish_create to see the values being generated.

Back to the zipper. Walking into the left subtree, as in the example above, involves moving the focus to the left subtree, and noting the node and the right subtree in the path component.

Going down the right subtree is similar:

Going up is the inverse of goDownLeft and goDownRight.

And we might want to go all the way up:

Now we’d like to check with QuickCheck that going down an arbitrary path through a tree, then going all the way back up should bring us back to the same tree. So we will have to create random trees, paired with random paths through those trees. A tuple of type (Tree, Zipper) could work, but runs into dramas with overlapping instances since QuickCheck provides an instance for types, namely Arbitrary (a, b).

As a work-around, make a data type that holds a tree and a zipper:

Here is the instance of Arbitrary:

Now with this instance we can encode the test that going down in a tree and then back up brings us back to the same tree.

Check it:

*Zipper> quickCheck prop_zip_unzip
+++ OK, passed 100 tests.


Using verboseCheck we can see some of the values. Here is a sample:

(lots of output...)

TreeAndZipper (Node (Node (Node (Node (Node (Node (Node Empty (-7) (Node (Node (Node (Node Empty 88 (Node Empty (-79) Empty)) 82 (Node (Node Empty (-20) Empty) (-15) (Node Empty (-94) Empty))) (-60) Empty) 55 (Node Empty 0 Empty))) 6 (Node Empty (-7) Empty)) (-18) (Node Empty (-80) (Node Empty 60 Empty))) (-35) (Node Empty (-73) Empty)) (-32) (Node (Node (Node (Node (Node Empty (-71) Empty) 30 (Node (Node Empty 0 Empty) (-68) (Node Empty 91 Empty))) 1 (Node Empty (-46) (Node Empty (-41) (Node (Node Empty 93 Empty) 79 (Node (Node Empty 48 (Node (Node Empty 46 Empty) 76 (Node (Node Empty (-57) (Node Empty 90 Empty)) 34 (Node Empty (-11) (Node Empty (-10) Empty))))) 55 (Node Empty 65 (Node (Node (Node (Node Empty 2 (Node Empty 11 (Node Empty 34 Empty))) (-69) Empty) 68 Empty) 49 (Node Empty (-67) (Node (Node Empty 73 (Node Empty 59 (Node (Node Empty (-28) Empty) (-22) Empty))) (-15) Empty))))))))) 39 (Node Empty 40 (Node (Node (Node (Node Empty 88 Empty) 60 Empty) (-87) Empty) 53 Empty))) (-43) (Node Empty (-16) Empty))) 54 (Node Empty 73 Empty)) (-31) Empty) (Zipper (Node (Node (Node (Node (Node (Node Empty (-7) (Node (Node (Node (Node Empty 88 (Node Empty (-79) Empty)) 82 (Node (Node Empty (-20) Empty) (-15) (Node Empty (-94) Empty))) (-60) Empty) 55 (Node Empty 0 Empty))) 6 (Node Empty (-7) Empty)) (-18) (Node Empty (-80) (Node Empty 60 Empty))) (-35) (Node Empty (-73) Empty)) (-32) (Node (Node (Node (Node (Node Empty (-71) Empty) 30 (Node (Node Empty 0 Empty) (-68) (Node Empty 91 Empty))) 1 (Node Empty (-46) (Node Empty (-41) (Node (Node Empty 93 Empty) 79 (Node (Node Empty 48 (Node (Node Empty 46 Empty) 76 (Node (Node Empty (-57) (Node Empty 90 Empty)) 34 (Node Empty (-11) (Node Empty (-10) Empty))))) 55 (Node Empty 65 (Node (Node (Node (Node Empty 2 (Node Empty 11 (Node Empty 34 Empty))) (-69) Empty) 68 Empty) 49 (Node Empty (-67) (Node (Node Empty 73 (Node Empty 59 (Node (Node Empty (-28) Empty) (-22) Empty))) (-15) Empty))))))))) 39 (Node Empty 40 (Node (Node (Node (Node Empty 88 Empty) 60 Empty) (-87) Empty) 53 Empty))) (-43) (Node Empty (-16) Empty))) 54 (Node Empty 73 Empty)) (WentLeft Top (-31) Empty))
Passed:
TreeAndZipper (Node Empty (-33) Empty) (Zipper (Node Empty (-33) Empty) Top)
Passed:
TreeAndZipper Empty (Zipper Empty Top)
Passed:
TreeAndZipper (Node Empty (-95) Empty) (Zipper (Node Empty (-95) Empty) Top)
+++ OK, passed 100 tests.


Traversals with a zipper

A nifty thing about zippers is that we can use them to step through a traversal, controlling the process programatically. If we are walking through a tree, we might be finished, or we have produced a value (an Int) but need to keep going through the zipper:

The step function converts a zipper into this state (step) type:

If we have an empty tree and no path, we are done.

If we have gone down-left, make note of the node’s value x and the rest of the zipper:

Otherwise, we have a tree and a path, so try to continue by going down-left:

In summary:

By repeatedly applying step we get an inorder traversal of the tree:

(As an aside, runStep is tail recursive.)

Using inorder on our example tree:

*Zipper> inorder tree
[1,2,3,4]


Here is a plain recursive definition of an inorder traversal:

We can use this to verify that our fancy zipper inorder traversal is correct:

Testing it:

*Zipper> quickCheck prop_inorder
+++ OK, passed 100 tests.


If we want to do something different in the traversal, for example running a monadic action, we can use the same Step datatype and change the definition of runStep:

Example usage:

*Zipper> inorderM (\x -> putStrLn $"Node value: " ++ show x) tree Node value: 1 Node value: 2 Node value: 3 Node value: 4  Mapping over a tree If we want to apply a function to each value in a tree, a recursive definition might be: *Zipper> tree Node (Node Empty 1 Empty) 2 (Node Empty 3 (Node Empty 4 Empty)) *Zipper> mapTree (+1) tree Node (Node Empty 2 Empty) 3 (Node Empty 4 (Node Empty 5 Empty))  We can check that mapTree id == mapTree: *Zipper> quickCheck prop_maptree +++ OK, passed 100 tests.  We can also use a zipper to map over the tree by using a different data type to represent the stepping: Testing it: *Zipper> tree Node (Node Empty 1 Empty) 2 (Node Empty 3 (Node Empty 4 Empty)) *Zipper> mapTree' (+1) tree Node (Node Empty 2 Empty) 3 (Node Empty 4 (Node Empty 5 Empty))  And testing it using QuickCheck: *Zipper> quickCheck prop_maptree' +++ OK, passed 100 tests.  The Main.hs file runs all the tests: $ ghc --make Main.hs
[1 of 2] Compiling Zipper           ( Zipper.lhs, Zipper.o )
[2 of 2] Compiling Main             ( Main.hs, Main.o )