From b7801991967a3ca88aaa238169eec3a63d916bcb Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Fri, 26 Nov 2010 20:41:06 -0500 Subject: [PATCH] zipper -> week11 Signed-off-by: Jim Pryor --- assignment8.mdwn | 61 ++++++++++++++++++++++++++++++++++++++++++++++ index.mdwn | 4 ++- new_stuff.mdwn | 2 +- zipper.mdwn => week11.mdwn | 0 4 files changed, 65 insertions(+), 2 deletions(-) create mode 100644 assignment8.mdwn rename zipper.mdwn => week11.mdwn (100%) diff --git a/assignment8.mdwn b/assignment8.mdwn new file mode 100644 index 00000000..547db8ed --- /dev/null +++ b/assignment8.mdwn @@ -0,0 +1,61 @@ +1. Complete the definitions of `move_botleft` and `move_right_or_up` from the same-fringe solution in the [[week11]] notes. Test your attempts against some example trees to see if the resulting `make_fringe_enumerator` and `same_fringe` functions work as expected. + + type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree) + + 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 };; + + 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) *) + YOU SUPPLY THE DEFINITION + + + let rec move_right_or_up (z : 'a zipper) : 'a zipper option = + (* if it's possible to move right in z, returns Some (the result of doing so) *) + (* else if it's not possible to move any further up in z, returns None *) + (* else returns move_right_or_up (result of moving up in z) *) + YOU SUPPLY THE DEFINITION + + + let new_zipper (t : 'a tree) : 'a zipper = + {tree = Root; filler = t} + ;; + + 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 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 + (* update zcell to point to next leaf, if there is one *) + in let () = zcell := match move_right_or_up z with + | None -> None + | Some z' -> Some (move_botleft z') + (* return saved label *) + in Some current + ) + (* return the next_leaf function *) + in next_leaf + ;; + + let same_fringe (t1 : 'a tree) (t2 : 'a tree) : bool = + let next1 = make_fringe_enumerator t1 + in let next2 = make_fringe_enumerator t2 + in let rec loop () : bool = + match next1 (), next2 () with + | Some a, Some b when a = b -> loop () + | None, None -> true + | _ -> false + in loop () + ;; + diff --git a/index.mdwn b/index.mdwn index f4335f96..f746e61f 100644 --- a/index.mdwn +++ b/index.mdwn @@ -65,7 +65,9 @@ preloaded is available at [[assignment 3 evaluator]]. > Topics: Calculator Improvements, including mutation -(30 Nov) Lecture notes for Week11 +(30 Nov) Lecture notes for Week11; Assignment8. + +> Topics: Zippers, Continuations (6 Dec) Lecture notes for Week12 diff --git a/new_stuff.mdwn b/new_stuff.mdwn index fd0b7bfc..8a74c059 100644 --- a/new_stuff.mdwn +++ b/new_stuff.mdwn @@ -2,6 +2,6 @@ Page for Chris and Jim to see what each other is working on, but hasn't necessar [[Week10]] -[[Zipper]] +[[Week11]] diff --git a/zipper.mdwn b/week11.mdwn similarity index 100% rename from zipper.mdwn rename to week11.mdwn -- 2.11.0