+<!-- λ ◊ ≠ ∃ Λ ∀ ≡ α β γ ρ ω φ ψ Ω ○ μ η δ ζ ξ ⋆ ★ • ∙ ● ⚫ 𝟎 𝟏 𝟐 𝟘 𝟙 𝟚 𝟬 𝟭 𝟮 ⇧ (U+2e17) ¢ -->
+
[[!toc]]
##List 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.
+
+<pre>
+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
+</pre>
+
+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:
+
+<pre>
+# 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
+</pre>
-##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.
-
-It's important to set some ground rules for what will follow. If you don't understand these ground rules you will get confused. First off, for many uses of trees one wants some of the nodes or leaves in the tree to be *labeled* with additional information. It's important not to conflate the label with the node itself. Numerically one and the same piece of information --- for example, the same `int` --- could label two nodes of the tree without those nodes thereby being identical, as here:
-
- root
- / \
- / \
- / \ label 10
- / \
- label 10 label 20
-
-The leftmost leaf and the rightmost leaf have the same label; but they are different leaves. The leftmost leaf has a sibling leaf with the label `20`; the rightmost leaf has no siblings that are leaves. Sometimes when one is diagramming trees, one will annotate the nodes with the labels, as above. Other times, when one is diagramming trees, one will instead want to annotate the nodes with tags to make it easier to refer to particular parts of the tree. So for instance, I could diagram the same tree as above as:
-
- 1
- / \
- 2 \
- / \ 5
- / \
- 3 4
-
-Here I haven't drawn what the labels are. The leftmost leaf, the node tagged "3" in this diagram, doesn't have the label `3`. It has the label `10`, as we said before. I just haven't put that into the diagram. The node tagged "2" doesn't have the label `2`. It doesn't have any label. The tree in this example only has information labeling its leaves, not any of its inner nodes. The identity of its inner nodes is exhausted by their position in the tree.
-
-That is a second thing to note. In what follows, we'll only be working with *leaf-labeled* trees. In some uses of trees, one also (or sometimes, only) wants labels on inner nodes. But we won't be discussing any such trees now. Our trees only have labels on their leaves. The diagrams below will tag all of the nodes, as in the second diagram above, and won't display what the leaves' labels are.
-
-Final introductory comment: in particular applications, you may only need to work with binary trees---trees where internal nodes always have exactly two subtrees. That is what we'll work with in the homework, for example. But to get the guiding idea of how tree zippers work, it's helpful first to think about trees that permit nodes to have many subtrees. So that's how we'll start.
-
-Suppose we have the following tree:
-
- 9200
- / | \
- / | \
- / | \
- / | \
- / | \
- 500 920 950
- / | \ / | \ / | \
- 20 50 80 91 92 93 94 95 96
- 1 2 3 4 5 6 7 8 9
-
-This is a leaf-labeled tree whose labels aren't displayed. The `9200` and so on are tags to make it easier for us to refer to particular parts of the tree.
-
-Suppose we want to represent that we're *at* the node marked `50`. We might use the following metalanguage notation to specify this:
-
- in_focus = subtree rooted at 50,
- context = (up = ..., left_siblings = [subtree rooted at 20], right_siblings = [subtree rooted at 80])
-
-This is modeled on the notation suggested above for list zippers. Here "subtree rooted at 20" means the whole subtree underneath node `20`:
- 20
- / | \
- 1 2 3
-For brevity, we'll just call this `subtree 20`; and similarly for `subtree 50` and `subtree 80`. We'll also abbreviate `left_siblings = [subtree 20], right_siblings = [subtree 80]` to just:
-
- siblings = [subtree 20; *; subtree 80]
-
-The `*` marks where the left siblings stop and the right siblings start.
-
-We haven't said yet what goes in the `up = ...` slot. But if you think about it, the parent of the context centered on `node 50` should intuitively be the context centered on `node 500`:
-
- (up = ..., siblings = [*; subtree 920; subtree 950])
-
-And the parent of that context should intuitively be a context centered on `node 9200`. This context has no left or right siblings, and there is no going further up from it. So let's mark it as a special context, that we'll call:
-
- Root
-
-Fully spelled out, then, our tree focused on `node 50` would look like this:
-
- in_focus = subtree 50,
- context = (up = (up = Root,
- siblings = [*; subtree 920; subtree 950]),
- siblings = [subtree 20; *; subtree 80])
-
-For brevity, we may sometimes write like this, using ellipsis and such:
-
- up = ..., siblings = [subtree 20; *; subtree 80], * filled by subtree 50
-
-But that should be understood as standing for the more fully-spelled-out structure.
-
-Structures of this sort are called **tree zippers**. They should already seem intuitively similar to list zippers, at least in what we're using them to represent. It may also be helpful to call them **focused trees**, though, and so will be switching back and forth between these different terms.
+##Tree Zippers##
-Moving left in our tree focused on `node 50` would be a matter of shifting the `*` leftwards:
+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.
- up = ..., siblings = [*; subtree 50; subtree 80], * filled by subtree 20
+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.
-and similarly for moving right. If the sibling list is implemented as a list zipper, you should already know how to do that. 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.
+In order to emphasize the similarity with list zippers, we'll use
+trees that are conceived of as lists of lists:
-Moving downward in the tree would be a matter of constructing a tree focused on some child of `node 20`, with the context part of the focused tree above (everything but the specification of the element in focus) as its `up`:
+ type tree = Leaf of int | Branch of tree list
- up = (up = ..., siblings = [*; subtree 50; subtree 80]),
- siblings = [*; leaf 2; leaf 3],
- * filled by leaf 1
+On this conception, a tree is nothing more than a list of subtrees.
+For instance, we might have
-How would we move upward in a tree? Well, to move up from the focused tree just displayed (focused on leaf `1`), we'd build a regular, unfocused tree with a root node --- let's call it `20'` --- whose children are given by the outermost sibling list in the focused tree above (`[*; leaf 2; leaf 3]`), after inserting the currently focused subtree (`leaf 1`) into the `*` position:
+ let t1 = Branch [Leaf 1; Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]];;
- node 20'
- / | \
- / | \
- leaf 1 leaf 2 leaf 3
+ _|__
+ | |
+ 1 |
+ _|__
+ | |
+ | 4
+ _|__
+ | |
+ 2 3
-Call the unfocused tree just specified `subtree 20'`. (It's the same as `subtree 20` was before. We just give it a different name because `subtree 20` wasn't a component we could extract from the previous zipper. We had to rebuild it from the information the previous zipper encoded.) The result of moving upward from our previous focused tree, focused on `leaf 1`, would be a tree focused on the subtree just described, with the context being the outermost `up` element of the previous focused tree (what's written above as `(up = ..., siblings = [*; subtree 50; subtree 80])`. That is:
+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.
- up = ...,
- siblings = [*; subtree 50; subtree 80],
- * filled by subtree 20'
+ _*__
+ | |
+ 1 |
+ _|__
+ | |
+ | 4
+ _|__
+ | |
+ 2 3
-Or, spelling that structure out fully:
+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).
- in_focus = subtree 20',
- context = (up = (up = Root,
- siblings = [*; subtree 920; subtree 950]),
- siblings = [*; subtree 50; subtree 80])
+ _|__
+ | |
+ 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:
-Moving upwards yet again would get us:
+ [2;3], ([] [4] ([1], [], Root))
- in_focus = subtree 500',
- context = (up = Root,
- siblings = [*; subtree 920; subtree 950])
+ ≡ (Branch [Leaf 2; Leaf 3],
+ Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))
-where `subtree 500'` refers to a subtree built from a root node whose children are given by the list `[*; subtree 50; subtree 80]`, with `subtree 20'` inserted into the `*` position. Moving upwards yet again would get us:
+Then we can take a tour of the original tree like this:
- in_focus = subtree 9200',
- context = Root
+<pre>
+_|__
+| |
+1 |
+ _|__
+ | |
+ | 4
+ _|__
+ | |
+ 2 3
-where the focused node is exactly the root of our complete tree. Like the "moving backward" operation for the list zipper, this "moving upward" operation is supposed to be reminiscent of closing a zipper, and that's why these data structures are called zippers.
+ [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)))
+</pre>
-We haven't given you an executable implementation of the tree zipper, but only a suggestive notation. We have however told you enough that you should be able to implement it yourself. Or if you're lazy, you can read:
+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.
-
-