prep ass10 for more hints

[lambda.git] / tree_and_list_zippers.mdwn

diff --git a/tree_and_list_zippers.mdwn b/tree_and_list_zippers.mdwn
index 5d26ca9..1eb5d07 100644 (file)
--- a/tree_and_list_zippers.mdwn
+++ b/tree_and_list_zippers.mdwn
@@ -5,28 +5,28 @@
 Say you've got some moderately-complex function for searching through a list, for example:
 
        let find_nth (test : 'a -> bool) (n : int) (lst : 'a list) : (int * 'a) ->
 Say you've got some moderately-complex function for searching through a list, for example:
 
        let find_nth (test : 'a -> bool) (n : int) (lst : 'a list) : (int * 'a) ->

-               let rec helper (position : int) n lst =
-                       match lst with
-                       | [] -> failwith "not found"
-                       | x :: xs when test x -> (if n = 1
-                               then (position, x)
-                               else helper (position + 1) (n - 1) xs
-                       )
-                       | x :: xs -> helper (position + 1) n xs
-               in helper 0 n lst;;
+           let rec helper (position : int) n lst =
+               match lst with
+               | [] -> failwith "not found"
+               | x :: xs when test x -> (if n = 1
+                   then (position, x)
+                   else helper (position + 1) (n - 1) xs
+               )
+               | 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:
 
        let find_nth' (test : 'a -> bool) (n : int) (lst : 'a list) (default : 'a) : ('a * 'a * 'a) ->
 
 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:
 
        let find_nth' (test : 'a -> bool) (n : int) (lst : 'a list) (default : 'a) : ('a * 'a * 'a) ->

-               let rec helper (predecessor : 'a) n lst =
-                       match lst with
-                       | [] -> failwith "not found"
-                       | x :: xs when test x -> (if n = 1
-                               then (predecessor, x, match xs with [] -> default | y::ys -> y)
-                               else helper x (n - 1) xs
-                       )
-                       | x :: xs -> helper x n xs
-               in helper default n lst;;
+           let rec helper (predecessor : 'a) n lst =
+               match lst with
+               | [] -> failwith "not found"
+               | x :: xs when test x -> (if n = 1
+                   then (predecessor, x, match xs with [] -> default | y::ys -> y)
+                   else helper x (n - 1) xs
+               )
+               | x :: xs -> helper x n xs
+           in helper default n lst;;

 
 This duplicates a lot of the structure of `find_nth`; it just has enough different code to retrieve different information when the matching element is found. But now what if you wanted to retrieve yet a different kind of information...?
 
 
 This duplicates a lot of the structure of `find_nth`; it just has enough different code to retrieve different information when the matching element is found. But now what if you wanted to retrieve yet a different kind of information...?
 


@@ -66,7 +66,7 @@ The kind of data structure we're looking for here is called a **list zipper**. T
 
 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 "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.)
 

-We had some discussio 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:
+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:

 
                 t
                  a
 
                 t
                  a


@@ -93,7 +93,7 @@ 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.
 
 
 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
                / \
 
                root
                / \


@@ -102,7 +102,7 @@ It's important to set some ground rules for what will follow. If you don't under
          /      \
        label 1  label 2
 
          /      \
        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
                / \
 
                 1
                / \


@@ -111,9 +111,9 @@ The leftmost leaf and the rightmost leaf have the same label; but they are diffe
          /      \
         3        4
 
          /      \
         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.
 
 
 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.
 


@@ -247,6 +247,7 @@ where the targetted element is the root of our base tree. Like the "moving backw
 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)]]
 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.
 
 *      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.