## List Zippers

Say you've got some moderately-complex function for searching through a list, for example:

let find_nth (test : 'a -> bool) (n : int) (lst : 'a list) : (int * 'a) ->
let rec helper (position : int) n lst =
match lst with
| x :: xs when test x -> (if n = 1
then (position, x)
else helper (position + 1) (n - 1) xs
)
| x :: xs -> helper (position + 1) n xs
in helper 0 n lst;;


This searches for the nth element of a list that satisfies the predicate test, and returns a pair containing the position of that element, and the element itself. (We follow the dominant convention of counting list positions from the left starting at 0.) Good. But now what if you wanted to retrieve a different kind of information, such as the nth element matching test, together with its preceding and succeeding elements? In a real situation, you'd want to develop some good strategy for reporting when the target element doesn't have a predecessor and successor; but we'll just simplify here and report them as having some default value:

let find_nth' (test : 'a -> bool) (n : int) (lst : 'a list) (default : 'a) : ('a * 'a * 'a) ->
let rec helper (predecessor : 'a) n lst =
match lst with
| x :: xs when test x -> (if n = 1
then (predecessor, x, match xs with [] -> default | y::ys -> y)
else helper x (n - 1) xs
)
| x :: xs -> helper x n xs
in helper default n lst;;


This duplicates a lot of the structure of find_nth; it just has enough different code to retrieve different information when the matching element is found. But now what if you wanted to retrieve yet a different kind of information...?

Ideally, there should be some way to factor out the code to find the target element---the nth element of the list satisfying the predicate test---from the code that retrieves the information you want once the target is found. We might build upon the initial find_nth function, since that returns the position of the matching element. We could hand that result off to some other function that's designed to retrieve information of a specific sort surrounding that position. But suppose our list has millions of elements, and the target element is at position 600512. The search function will already have traversed 600512 elements of the list looking for the target, then the retrieval function would have to start again from the beginning and traverse those same 600512 elements again. It could go a bit faster, since it doesn't have to check each element against test as it traverses. It already knows how far it has to travel. But still, this should seem a bit wasteful.

Here's an idea. What if we had some way of representing a list as "broken" at a specific point. For example, if our base list is:

[10; 20; 30; 40; 50; 60; 70; 80; 90]


we might imagine the list "broken" at position 3 like this:

            40;
30;     50;
20;             60;
[10;                    70;
80;
90]


Then if we move one step forward in the list, it would be "broken" at position 4:

                50;
40;     60;
30;             70;
20;                     80;
[10;                            90]


If we had some convenient representation of these "broken" lists, then our search function could hand that off to the retrieval function, and the retrieval function could start right at the position where the list was broken, without having to start at the beginning and traverse many elements to get there. The retrieval function would also be able to inspect elements both forwards and backwards from the position where the list was "broken".

The kind of data structure we're looking for here is called a list zipper. To represent our first broken list, we'd use two lists: (1) containing the elements in the left branch, preceding the target or focused element, in the order reverse to their appearance in the base list. (2) containing the target or focus element and the rest of the list, in normal order. So:

            40;
30;     50;
20;             60;
[10;                    70;
80;
90]


would be represented as ([30; 20; 10], [40; 50; 60; 70; 80; 90]). To move forward in the base list, we pop the head element 40 off of the head element of the second list in the zipper, and push it onto the first list, getting ([40; 30; 20; 10], [50; 60; 70; 80; 90]). To move backwards again, we pop off of the first list, and push it onto the second. To reconstruct the base list, we just "moved backwards" until the first list is empty. (This is supposed to evoke the image of zipping up a zipper; hence the data structure's name.)

Last time we gave the class, we had some discussion of what's the right way to apply the "zipper" metaphor. I suggest it's best to think of the tab of the zipper being here:

         t
a
b
40;
30;     50;
20;             60;
[10;                    70;
80;
90]


And imagine that you're just seeing the left half of a real-zipper, rotated 60 degrees counter-clockwise. When the list is all "zipped up", we've "move backwards" to the state where the first element is targeted or in focus:

([], [10; 20; 30; 40; 50; 60; 70; 80; 90])


However you understand the "zipper" metaphor, this is a very handy data structure, and it will become even more handy when we translate it over to more complicated base structures, like trees. To help get a good conceptual grip on how to do that, it's useful to introduce a kind of symbolism for talking about zippers. This is just a metalanguage notation, for us theorists.

[10; 20; 30; *; 50; 60; 70; 80; 90], * filled by 40


would represent a list zipper where the break is at position 3, and the element occupying that position is 40. For a list zipper, this could be implemented using the pairs-of-lists structure described above.

Alternatively, we could present it in a form more like we used in the seminar for tree zippers:

in_focus = 40, context = (before = [30; 20; 10], after = [50; 60; 70; 80; 90])


In order to facilitate the discussion of tree zippers, let's consolidate a bit with a concrete implementation.

type int_list_zipper = int * (int list) * (int list)
let zip_open (z:int_list_zipper):int_list_zipper = match z with
focus, ls, r::rs -> r, focus::ls, rs
| _ -> z
let zip_closed (z:int_list_zipper):int_list_zipper = match z with
focus, l::ls, rs -> l, ls, focus::rs


Here, an int list zipper is an int list with one element in focus. The context of that element is divided into two subparts: the left context, which gives the elements adjacent to the focussed element first (so looks reversed relative to the original list); and the right context, which is just the remainder of the list to the right of the focussed element.

Then we have the following behavior:

# let z1:int_list_zipper = 1, [], [2;3;4];;
val z1 : int_list_zipper = (1, [], [2; 3; 4])
# let z2 = zip_open z1;;
val z2 : int_list_zipper = (2, [1], [3; 4])
# let z3 = zip_open z2;;
val z3 : int_list_zipper = (3, [2; 1], [4])
# let z4 = zip_closed (zip_closed z3);;
val z4 : int_list_zipper = (1, [], [2; 3; 4])
# z4 = z1;;
# - : bool = true


## Tree Zippers

Now how could we translate a zipper-like structure over to trees? What we're aiming for is a way to keep track of where we are in a tree, in the same way that the "broken" lists let us keep track of where we are in the base list.

Thus tree zippers are analogous to list zippers, but with one additional dimension to deal with: in addition to needing to shift focus to the left or to the right, we want to be able to shift the focus up or down.

In order to emphasize the similarity with list zippers, we'll use trees that are conceived of as lists of lists:

type tree = Leaf of int | Branch of tree list


On this conception, a tree is nothing more than a list of subtrees. For instance, we might have

let t1 = Branch [Leaf 1; Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]];;

_|__
|  |
1  |
_|__
|  |
|  4
_|__
|  |
2  3


For simplicity, we'll work with trees that don't have labels on their internal nodes. Note that there can be any number of siblings, though we'll work with binary trees here to prevent clutter.

_*__
|  |
1  |
_|__
|  |
|  4
_|__
|  |
2  3


How should we represent a tree with the starred subtree in focus? Well, that's easy: the focussed element is the entire tree, and the context is null. We'll represent this as the ordered pair (t1, Root).

_|__
|  |
1  |
_*__
|  |
|  4
_|__
|  |
2  3


How should we represent a tree with this other starred subtree in focus? Well, viewing this tree as a list of subtrees, we've merely put the second element of the list in focus. We can almost just use the list zipper technique from the previous section:

Branch (Branch (Leaf 2, Leaf 3), Leaf 4), ([Leaf 1], [])


This is just a list zipper where the list elements are trees instead of ints.

But this won't be quite enough if we go one more level down.

_|__
|  |
1  |
_|__
|  |
|  4
_*__
|  |
2  3


The focussed element is the subtree Branch (Leaf 2, Leaf 3). And we know how to represent the part of the context that involves the siblings of the focussed tree:

Branch (Leaf 2, Leaf 3), ([], [Leaf 4])


We still need to add the rest of the context. But we just computed that context a minute ago. It was ([Leaf 1], []). If we add it here, we get:

Branch (Leaf 2, Leaf 3), ([], [Leaf 4], ([Leaf 1], [])


Here's the type suggested by this idea:

type context = Root | Context of (tree list) * (tree list) * context
type zipper = tree * context


We can gloss the triple (tree list) * (tree list) * context as (left siblings) * (right siblings) * (context of parent).

Here, then, is the full tree zipper we've been looking for:

(Branch [Leaf 2; Leaf 3],
Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))


Just as with the simple list zipper, note that elements that are near the focussed element in the tree are near the focussed element in the zipper representation. This is what makes it easy to shift the focus to nearby elements in the tree.

It should be clear that moving left and right in the tree zipper is just like moving left and right in a list zipper.

Moving down requires looking inside the tree in focus, and grabbing hold of one of its subtrees. Since that subtree is the new focus, its context will be the list zipper consisting of its siblings (also recovered from the original focus).

let downleft (z:zipper):zipper = match z with
(Branch (l::rest)), context -> l, Context ([], rest, context)


Moving up involves gathering up the left and right siblings and re-building the original subtree. It's easiest to do this when the sibling zipper is fully closed, i.e., when the list of left siblings is empty:

let rec up (z:zipper):zipper = match z with
focus, Context ([], rs, rest) -> Branch (focus::rs), rest
| focus, Context (l::ls, _, _) -> up (left z)


The second match says that if the list of left siblings isn't empty, we just shift focus left and try again.

This tree zipper works for trees with arbitrary numbers of siblings per subtree. If one were designing a tree zipper for a more restricted kind of tree, however, such as a binary tree, one would probably not represent siblings with a list zipper, but with something more special-purpose and economical.

With these functions, we can refocus on any part of the tree. Let's abbreviate a tree zipper like this:

[2;3], ([] [4] ([1], [], Root))

≡ (Branch [Leaf 2; Leaf 3],
Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))


Then we can take a tour of the original tree like this:

_|__
|  |
1  |
_|__
|  |
|  4
_|__
|  |
2  3

[1;[[2;3];4]],Root           =                                                              [1;[[2;3];4]],Root
downleft                                                                                               up
1, ([],[[2;3];4],Root) right [[2;3];4],([1],[],Root)                                            [[2;3];4],([1],[],Root)
downleft                                                                      up
[2;3],([],[4],([1],[],Root))         [2;3],([],[4],([1],[],Root)) right 4,([2;3],[],([1],[],Root))
downleft                                           up
2, ([],[3],([],[4],([1],[],Root))) right 3, ([2],[],([],[4],([1],[],Root)))


Here's more on zippers: