+ _*__
+ | |
+ 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.
+Here's a complete tour:
+
+<pre>
+# let z1 = (t1, Root);;
+val z1 : zipper =
+ (Branch [Leaf 1; Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]], Root)
+# let z2 = downleft z1;;
+val z2 : zipper =
+ (Leaf 1, Context ([], [Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]], Root))
+# let z3 = right z2;;
+val z3 : zipper =
+ (Branch [Branch [Leaf 2; Leaf 3]; Leaf 4], Context ([Leaf 1], [], Root))
+# let z4 = downleft z3;;
+val z4 : zipper =
+ (Branch [Leaf 2; Leaf 3],
+ Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))
+# let z5 = downleft z4;;
+val z5 : zipper =
+ (Leaf 2,
+ Context ([], [Leaf 3],
+ Context ([], [Leaf 4], Context ([Leaf 1], [], Root))))
+# let z6 = right z5;;
+val z6 : zipper =
+ (Leaf 3,
+ Context ([Leaf 2], [],
+ Context ([], [Leaf 4], Context ([Leaf 1], [], Root))))
+# let z7 = up z6;;
+val z7 : zipper =
+ (Branch [Leaf 2; Leaf 3],
+ Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))
+# let z8 = right z7;;
+val z8 : zipper =
+ (Leaf 4,
+ Context ([Branch [Leaf 2; Leaf 3]], [], Context ([Leaf 1], [], Root)))
+# let z9 = up z8;;
+val z9 : zipper =
+ (Branch [Branch [Leaf 2; Leaf 3]; Leaf 4], Context ([Leaf 1], [], Root))
+# let z10 = up z9;;
+val z10 : zipper =
+ (Branch [Leaf 1; Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]], Root)
+# z10 = z1;;
+- : bool = true
+# z10 == z1;;
+- : bool = false
+</pre>
+
+Here's more on zippers: