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 leafs 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:
+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 1 label 2
-The leftmost leaf and the rightmost leaf have the same label; but they are different leafs. The leftmost leaf has a sibling leaf with the label 2; the rightmost leaf has no siblings that are leafs. 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:
+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 2; 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
/ \
/ \
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 1, 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 leafs, not any of its inner nodes. The identity of its inner nodes is exhausted by their position in the tree.
+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 1, 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 wants labels on inner nodes. But we won't be discussing any such trees now. Our trees only have labels on their leafs. The diagrams below will tag all of the nodes, as in the second diagram above, and won't display what the leafs' labels are.
+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 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.
We haven't given you a real 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:
* [[!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.