X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week11.mdwn;h=14d5eed2745a5ab8cb140fc76c09f477d93d47c6;hp=56a064bbf22a6f7e3d6b0ae321a84e1480230e6d;hb=8fbf14566363197bb08307a6bf4daece2f27602e;hpb=e3955b2351ea8fa5ea3bb09e59223806157d2368 diff --git a/week11.mdwn b/week11.mdwn index 56a064bb..14d5eed2 100644 --- a/week11.mdwn +++ b/week11.mdwn @@ -93,8 +93,6 @@ to represent a list zipper where the break is at position 3, and the element occ 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. -We're understanding the `20` here in `node 20` to just be a metalanguage marker to help us theorists keep track of which node we're referring to. We're supposing the tree structure itself doesn't associate any informative labelling information with those nodes. It only associates informative labels with the tree leafs. (We haven't represented any such labels in our diagrams.) - 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: root @@ -113,7 +111,7 @@ The leftmost leaf and the rightmost leaf have the same label; but they are diffe / \ 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 labels on its leafs, not on any of its inner nodes. +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. 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. @@ -150,7 +148,7 @@ Similarly for `subtree 50` and `subtree 80`. We haven't said yet what goes in th And the parent of that targetted subtree should intuitively be a tree targetted on `node 9200`: - {parent = None; siblings = [*]}, * filled by subtree 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: @@ -159,13 +157,13 @@ This tree has no parents because it's the root of the base tree. Fully spelled o parent = { parent = None; siblings = [*] - }, * filled by subtree 9200; + }, * 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 subtree 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: +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 = { @@ -185,7 +183,7 @@ 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**, for a reason that will emerge. They should already seem intuitively similar to list zippers, though, at least in what we're using them to represent. I think it may initially be more helpful to call these **targetted trees**, though, and so will be switching back and forth between this different terms. +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. Moving left in our targetted tree that's targetted on `node 50` would be a matter of shifting the `*` leftwards: @@ -237,12 +235,12 @@ Moving upwards yet again would get us: siblings = [*; subtree 920; subtree 950] }, * filled by subtree 500' -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: +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: { parent = None; siblings = [*] - }, * filled by subtree 9200' + }, * filled by tree 9200' 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. @@ -254,7 +252,7 @@ We haven't given you a real implementation of the tree zipper, but only a sugges ##Same-fringe using a tree zipper## -Recall back in [[Assignment4]], we asked you to enumerate the "fringe" of a leaf-labeled tree. Both of these trees: +Recall back in [[Assignment4]], we asked you to enumerate the "fringe" of a leaf-labeled tree. Both of these trees (here I *am* drawing the labels in the diagram): . . / \ / \ @@ -262,7 +260,7 @@ Recall back in [[Assignment4]], we asked you to enumerate the "fringe" of a leaf / \ / \ 1 2 2 3 -have the same fringe: `[1;2;3]`. We also asked you to write a function that determined when two trees have the same fringe. The way you approached that back then was to enumerate each tree's fringe, and then compare the two lists for equality. Today, and then again in a later class, we'll encounter two new ways to approach the problem of determining when two trees have the same fringe. +have the same fringe: `[1;2;3]`. We also asked you to write a function that determined when two trees have the same fringe. The way you approached that back then was to enumerate each tree's fringe, and then compare the two lists for equality. Today, and then again in a later class, we'll encounter new ways to approach the problem of determining when two trees have the same fringe. Supposing you did work out an implementation of the tree zipper, then one way to determine whether two trees have the same fringe would be: go downwards (and leftwards) in each tree as far as possible. Compare the targetted leaves. If they're different, stop because the trees have different fringes. If they're the same, then for each tree, move rightward if possible; if it's not (because you're at the rightmost position in a sibling list), more upwards then try again to move rightwards. Repeat until you are able to move rightwards. Once you do move rightwards, go downwards (and leftwards) as far as possible. Then you'll be targetted on the next leaf in the tree's fringe. The operations it takes to get to "the next leaf" may be different for the two trees. For example, in these trees: @@ -326,9 +324,10 @@ Here is how you can extract the components of a labeled record: Anyway, using record types, we might define the tree zipper interface like so: - type 'a starred_tree = Root | Starring_Left of 'a starred_pair | Starring_Right of 'a starred_pair - and 'a starred_pair = { parent : 'a starred_tree; sibling: 'a tree } - and 'a zipper = { tree : 'a starred_tree; filler: 'a tree };; + type 'a starred_level = Root | Starring_Left of 'a starred_nonroot | Starring_Right of 'a starred_nonroot + and 'a starred_nonroot = { parent : 'a starred_level; sibling: 'a tree };; + + type 'a zipper = { tree : 'a starred_level; filler: 'a tree };; let rec move_botleft (z : 'a zipper) : 'a zipper = (* returns z if the targetted node in z has no children *)