+<!-- λ ◊ ≠ ∃ Λ ∀ ≡ α β γ ρ ω φ ψ Ω ○ μ η δ ζ ξ ⋆ ★ • ∙ ● ⚫ 𝟎 𝟏 𝟐 𝟘 𝟙 𝟚 𝟬 𝟭 𝟮 ⇧ (U+2e17) ¢ -->
+
[[!toc]]
##List Zippers##
| x :: xs -> helper (position + 1) n xs
in helper 0 n lst;;
-This searches for the `n`th element of a list that satisfies the predicate `test`, and returns a pair containing the position of that element, and the element itself. Good. But now what if you wanted to retrieve a different kind of information, such as the `n`th 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:
+This searches for the `n`th 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 `n`th 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 =
[10; 20; 30; 40; 50; 60; 70; 80; 90]
-we might imagine the list "broken" at position 3 like this (positions are numbered starting from 0):
+we might imagine the list "broken" at position 3 like this:
40;
30; 50;
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 element, *in the order reverse to their appearance in the base list*. (2) containing the target element and the rest of the list, in normal order. So:
+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;
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 "move 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.)
+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.)
-We had some discussion in seminar of the right way to understand the "zipper" metaphor. I think it's best to think of the tab of the zipper being here:
+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
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 targetted:
-
- ([], [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; we don't need our programs to interpret the notation. We'll use a specification like this:
-
- [10; 20; 30; *; 50; 60; 70; 80; 90], * filled by 40
-
-to represent a list zipper where the break is at position 3, and the element occupying that position is 40. For a list zipper, this is implemented using the pairs-of-lists structure described above.
-
-
-##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 1
- / \
- label 1 label 2
-
-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
- / \
- 2 \
- / \ 5
- / \
- 3 4
+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:
-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.
+ ([], [10; 20; 30; 40; 50; 60; 70; 80; 90])
-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.
+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.
-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.
+ [10; 20; 30; *; 50; 60; 70; 80; 90], * filled by 40
-Suppose we have the following tree:
+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.
- 9200
- / | \
- / | \
- / | \
- / | \
- / | \
- 500 920 950
- / | \ / | \ / | \
- 20 50 80 91 92 93 94 95 96
- 1 2 3 4 5 6 7 8 9
+Alternatively, we could present it in a form more like we used in the seminar for tree zippers:
-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.
+ in_focus = 40, context = (before = [30; 20; 10], after = [50; 60; 70; 80; 90])
-Suppose we want to represent that we're *at* the node marked `50`. We might use the following metalanguage notation to specify this:
+In order to facilitate the discussion of tree zippers,
+let's consolidate a bit with a concrete implementation.
- {parent = ...; siblings = [subtree 20; *; subtree 80]}, * filled by subtree 50
+<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>
-This is modeled on the notation suggested above for list zippers. Here `subtree 20` refers to the whole subtree rooted at node `20`:
+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.
- 20
- / | \
- 1 2 3
+Then we have the following behavior:
-Similarly for `subtree 50` and `subtree 80`. We haven't said yet what goes in the `parent = ...` slot. Well, the parent of a subtree targetted on `node 50` should intuitively be a tree targetted on `node 500`:
+<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>
- {parent = ...; siblings = [*; subtree 920; subtree 950]}, * filled by subtree 500
-And the parent of that targetted subtree should intuitively be a tree targetted on `node 9200`:
- {parent = None; siblings = [*]}, * filled by tree 9200
-
-This tree has no parents because it's the root of the base tree. Fully spelled out, then, our tree targetted on `node 50` would be:
-
- {
- parent = {
- parent = {
- parent = None;
- siblings = [*]
- }, * filled by tree 9200;
- siblings = [*; subtree 920; subtree 950]
- }, * filled by subtree 500;
- siblings = [subtree 20; *; subtree 80]
- }, * filled by subtree 50
-
-In fact, there's some redundancy in this structure, at the points where we have `* filled by tree 9200` and `* filled by subtree 500`. Since node 9200 doesn't have any label attached to it, the subtree rooted in it is determined by the rest of this structure; and so too with `subtree 500`. So we could really work with:
-
- {
- parent = {
- parent = {
- parent = None;
- siblings = [*]
- },
- siblings = [*; subtree 920; subtree 950]
- },
- siblings = [subtree 20; *; subtree 80]
- }, * filled by subtree 50
-
-
-We still do need to keep track of what fills the outermost targetted position---`* filled by subtree 50`---because that contain a subtree of arbitrary complexity, that is not determined by the rest of this data structure.
-
-For simplicity, I'll continue to use the abbreviated form:
-
- {parent = ...; 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. I think it may also be helpful to call them **targetted trees**, though, and so will be switching back and forth between these different terms.
+##Tree Zippers##
-Moving left in our targetted tree that's targetted 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.
- {parent = ...; 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 targetted on some child of `node 20`, with the first part of the targetted tree above as its parent:
+ type tree = Leaf of int | Branch of tree list
- {
- parent = {parent = ...; 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, we'd build a regular, untargetted tree with a root node---let's call it `20'`---and whose children are given by the outermost sibling list in the targetted tree above, after inserting the targetted subtree 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
-We'll call this new untargetted tree `subtree 20'`. The result of moving upward from our previous targetted tree, targetted on `leaf 1`, would be the outermost `parent` element of that targetted tree, with `subtree 20'` being the subtree that fills that parent's target position `*`:
+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.
- {
- parent = ...;
- 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).
- {
- parent = {
- parent = {
- parent = None;
- siblings = [*]
- },
- siblings = [*; subtree 920; subtree 950]
- },
- siblings = [*; subtree 50; subtree 80]
- }, * filled by subtree 20'
+ _|__
+ | |
+ 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))
- {
- parent = {
- parent = None;
- siblings = [*]
- },
- siblings = [*; subtree 920; subtree 950]
- }, * filled by subtree 500'
+ ≡ (Branch [Leaf 2; Leaf 3],
+ Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))
-where `subtree 500'` refers to a tree 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:
- {
- parent = None;
- siblings = [*]
- }, * filled by tree 9200'
+<pre>
+_|__
+| |
+1 |
+ _|__
+ | |
+ | 4
+ _|__
+ | |
+ 2 3
-where the targetted element is the root of our base 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 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:
+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.
-
-