From: Jim Pryor Date: Sat, 27 Nov 2010 02:09:20 +0000 (-0500) Subject: tweak week11 X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=4c318c7fe4a19f8271864c47459996c8d30fbf99 tweak week11 Signed-off-by: Jim Pryor --- diff --git a/week11.mdwn b/week11.mdwn index 6a843c35..618d5f04 100644 --- a/week11.mdwn +++ b/week11.mdwn @@ -183,7 +183,7 @@ How would we move upward in a tree? Well, we'd build a regular, untargetted tree / | \ leaf 1 leaf 2 leaf 3 -We'll call this new untargetted tree `node 20`. The result of moving upward from our previous targetter tree, targetted on `leaf 1`, would be the outermost `parent` element of that targetted tree, with `node 20` being the subtree that fills that parent's target position `*`: +We'll call this new untargetted tree `node 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 `node 20` being the subtree that fills that parent's target position `*`: { parent = ...; @@ -240,7 +240,7 @@ Supposing you did work out an implementation of the tree zipper, then one way to you won't move upwards at the same steps. Keep comparing "the next leafs" until they are different, or you exhaust the leafs of only one of the trees (then again the trees have different fringes), or you exhaust the leafs of both trees at the same time, without having found leafs with different labels. In this last case, the trees have the same fringe. -If your trees are very big---say, millions of leaves---you can imagine how this would be quicker and more memory-efficient than traversing each tree to construct a list of its fringe, and then comparing the two lists so built to see if they're equal. For one thing, the zipper method can abort early if the fringes diverge early, without needing to traverse or built a list containing the rest of each tree's fringe. +If your trees are very big---say, millions of leaves---you can imagine how this would be quicker and more memory-efficient than traversing each tree to construct a list of its fringe, and then comparing the two lists so built to see if they're equal. For one thing, the zipper method can abort early if the fringes diverge early, without needing to traverse or build a list containing the rest of each tree's fringe. Let's sketch the implementation of this. We won't provide all the details for an implementation of the tree zipper, but we will sketch an interface for it. @@ -266,6 +266,8 @@ records let you attach descriptive labels to the components of the tuple: # type blah_record = { height : int; weight : int; char_tester : char -> bool };; # let b2 = { height = 1; weight = 2; char_tester = fun c -> c = 'M' };; val b2 : blah_record = {height = 1; weight = 2; char_tester = } + # let b3 = { height = 1; char_tester = (fun c -> c = 'K'); weight = 3 };; (* also works *) + val b3 : blah_record = {height = 1; weight = 3; char_tester = } These were the strategies to extract the components of an unlabeled tuple: