X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2F_assignment12.mdwn;fp=exercises%2F_assignment12.mdwn;h=f09556f075c06c75c835b94cbc2cb7ff1fedf6f1;hp=0000000000000000000000000000000000000000;hb=df2bc76a01104a5a0983b1fe16e073de7277f844;hpb=18a893a1567d4cc1db9826d4e1bb60588c71e1c9 diff --git a/exercises/_assignment12.mdwn b/exercises/_assignment12.mdwn new file mode 100644 index 00000000..f09556f0 --- /dev/null +++ b/exercises/_assignment12.mdwn @@ -0,0 +1,135 @@ +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. Show us some of your tests. + + type 'a tree = Leaf of 'a | Node of ('a tree * '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 from z to the leftmost child) *) + _____ + (* 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 = + {level = Root; filler = t} + ;; + +   + + let make_fringe_enumerator (t: 'a tree) = + (* 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 + | 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 + ) + | None -> (* we've finished enumerating the fringe *) + None + (* 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 () + ;; + + +2. Here's another implementation of the same-fringe function, in Scheme. It's taken from . It uses thunks to delay the evaluation of code that computes the tail of a list of a tree's fringe. It also involves passing "the rest of the enumeration of the fringe" as a thunk argument (`tail-thunk` below). Your assignment is to fill in the blanks in the code, **and also to supply comments to the code,** to explain what every significant piece is doing. Don't forget to supply the comments, this is an important part of the assignment. + + This code uses Scheme's `cond` construct. That works like this; + + (cond + ((test1 argument argument) result1) + ((test2 argument argument) result2) + ((test3 argument argument) result3) + (else result4)) + + is equivalent to: + + (if (test1 argument argument) + ; then + result1 + ; else + (if (test2 argument argument) + ; then + result2 + ; else + (if (test3 argument argument) + ; then + result3 + ; else + result4))) + + Some other Scheme details: + + * `#t` is true and `#f` is false + * `(lambda () ...)` constructs a thunk + * there is no difference in meaning between `[...]` and `(...)`; we just sometimes use the square brackets for clarity + * `'(1 . 2)` and `(cons 1 2)` are pairs (the same pair) + * `(list)` and `'()` both evaluate to the empty list + * `(null? lst)` tests whether `lst` is the empty list + * non-empty lists are implemented as pairs whose second member is a list + * `'()` `'(1)` `'(1 2)` `'(1 2 3)` are all lists + * `(list)` `(list 1)` `(list 1 2)` `(list 1 2 3)` are the same lists as the preceding + * `'(1 2 3)` and `(cons 1 '(2 3))` are both pairs and lists (the same list) + * `(pair? lst)` tests whether `lst` is a pair; if `lst` is a non-empty list, it will also pass this test; if `lst` fails this test, it may be because `lst` is the empty list, or because it's not a list or pair at all + * `(car lst)` extracts the first member of a pair / head of a list + * `(cdr lst)` extracts the second member of a pair / tail of a list + + Here is the implementation: + + (define (lazy-flatten tree) + (letrec ([helper (lambda (tree tail-thunk) + (cond + [(pair? tree) + (helper (car tree) (lambda () (helper _____ tail-thunk)))] + [else (cons tree tail-thunk)]))]) + (helper tree (lambda () _____)))) + + (define (stream-equal? stream1 stream2) + (cond + [(and (null? stream1) (null? stream2)) _____] + [(and (pair? stream1) (pair? stream2)) + (and (equal? (car stream1) (car stream2)) + _____)] + [else #f])) + + (define (same-fringe? tree1 tree2) + (stream-equal? (lazy-flatten tree1) (lazy-flatten tree2))) + + (define tree1 '(((1 . 2) . (3 . 4)) . (5 . 6))) + (define tree2 '(1 . (((2 . 3) . (4 . 5)) . 6))) + + (same-fringe? tree1 tree2) + +