X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week11.mdwn;h=81534fcd5046108f232438adaa3ac13f9bd3a2d4;hp=cc7af5e2b3aad3cdcd41fe8dfa3cf4cf12ffe64a;hb=3562cbe6843f487857521a01f5291a2e578a7ed9;hpb=11976c4200a22c3bb279e5efeebbadc3ab3b835a diff --git a/week11.mdwn b/week11.mdwn index cc7af5e2..81534fcd 100644 --- a/week11.mdwn +++ b/week11.mdwn @@ -235,7 +235,7 @@ 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; @@ -252,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): . . / \ / \ @@ -260,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: @@ -324,20 +324,21 @@ 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 = { level : '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 *) (* else returns move_botleft (zipper which results from moving down and left in z) *) @@ -348,12 +349,12 @@ Anyway, using record types, we might define the tree zipper interface like so: (* else returns move_right_or_up (result of moving up in z) *) @@ -361,22 +362,19 @@ Anyway, using record types, we might define the tree zipper interface like so: The following function takes an 'a tree and returns an 'a zipper focused on its root: let new_zipper (t : 'a tree) : 'a zipper = - {tree = Root; filler = t} + {level = Root; filler = t} ;; Finally, we can use a mutable reference cell to define a function that enumerates a tree's fringe until it's exhausted: let make_fringe_enumerator (t: 'a tree) = - (* create a zipper targetting the root of t *) - let zstart = new_zipper t - in let zbotleft = move_botleft zstart + (* create a zipper targetting the botleft of t *) + let zbotleft = move_botleft (new_zipper t) (* create a refcell initially pointing to zbotleft *) in let zcell = ref (Some zbotleft) (* construct the next_leaf function *) in let next_leaf () : 'a option = match !zcell with - | None -> (* we've finished enumerating the fringe *) - None | Some z -> ( (* extract label of currently-targetted leaf *) let Leaf current = z.filler @@ -386,6 +384,8 @@ Finally, we can use a mutable reference cell to define a function that enumerate | Some z' -> Some (move_botleft z') (* return saved label *) in Some current + | None -> (* we've finished enumerating the fringe *) + None ) (* return the next_leaf function *) in next_leaf