# Zippers

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 )
Linking Main ...
$ ./Main
prop_finish_createZipper
+++ OK, passed 100 tests.
prop_inorder
+++ OK, passed 100 tests.
prop_maptree
+++ OK, passed 100 tests.
prop_maptree'
+++ OK, passed 100 tests.
prop_zip_unzip
+++ OK, passed 100 tests.
```