From: Jim Pryor Date: Fri, 26 Nov 2010 16:20:59 +0000 (-0500) Subject: tweak zipper X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=cc66e546b2a06d36cbaf609b7790a063d8e2a074 tweak zipper Signed-off-by: Jim Pryor --- diff --git a/zipper.mdwn b/zipper.mdwn index 10918343..bcb2d8b2 100644 --- a/zipper.mdwn +++ b/zipper.mdwn @@ -83,7 +83,7 @@ to represent a list zipper where the break is at position 3, and the element occ ##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. 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: 1000 / | \ @@ -96,11 +96,11 @@ Now how could we translate a zipper-like structure over to trees? What we're aim 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 -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: 20 / | \ @@ -153,7 +153,7 @@ Or, if we only had labels on the leafs of our tree: 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.