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::rsHere, 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: * [[!wikipedia Zipper (data structure)]] * [Haskell wikibook on zippers](http://en.wikibooks.org/wiki/Haskell/Zippers) * Huet, Gerard. ["Functional Pearl: The Zipper"](http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf) Journal of Functional Programming 7 (5): 549-554, September 1997. * As always, [Oleg](http://okmij.org/ftp/continuations/Continuations.html#zipper) takes this a few steps deeper.