Signed-off-by: Jim Pryor <profjim@jimpryor.net>
-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. For simplicity, we'll only implement this for binary trees---trees where internal nodes always have exactly two subtrees. But to get the guiding idea, it's helpful first to think about trees which permit nodes to have many subtrees. Suppose we had the following tree:
+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. In a particular application, you may only need to implement this for binary trees---trees where internal nodes always have exactly two subtrees. But to get the guiding idea, it's helpful first to think about trees that permit nodes to have many subtrees. Suppose we have the following tree:
20 50 80 91 92 93 94 95 96
1 2 3 4 5 6 7 8 9
20 50 80 91 92 93 94 95 96
1 2 3 4 5 6 7 8 9
-and we want to represent that we're at the node labeled `50`. We might use the following metalanguage notation to specify this:
+and we want to represent that we're at the node marked `50`. We might use the following metalanguage notation to specify this:
{parent = ...; siblings = [node 20; *; node 80]}, * filled by node 50
{parent = ...; siblings = [node 20; *; node 80]}, * filled by node 50
-This is modeled on the notation suggested above for list zippers. Here `node 20` refers not to a `int` label attached to that node, but rather to the whole subtree rooted at that node:
+This is modeled on the notation suggested above for list zippers. Here `node 20` refers not to a `int` label associated with that node, but rather to the whole subtree rooted at that node:
siblings = [node 20; *; node 80]
}, * filled by node 50
siblings = [node 20; *; node 80]
}, * filled by node 50
-We're understanding the `20` here in `node 20` to just be a metalanguage tag 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 diagreams.)
+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 diagreams.)
We still do need to keep track of what fills the outermost targetted position---`* filled by node 50`---because that contain a subtree of arbitrary complexity, that is not determined by the rest of this data structure.
We still do need to keep track of what fills the outermost targetted position---`* filled by node 50`---because that contain a subtree of arbitrary complexity, that is not determined by the rest of this data structure.