X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment8.mdwn;h=f09556f075c06c75c835b94cbc2cb7ff1fedf6f1;hp=cdb32e875beaa8cbab5f6e2171ce08f6814ae62e;hb=fff7086c5dec8448c3a5369f3df88b50ffd06e6b;hpb=eb2fa58d13fb86ca9ae981a85864374df7d864a7 diff --git a/assignment8.mdwn b/assignment8.mdwn index cdb32e87..f09556f0 100644 --- a/assignment8.mdwn +++ b/assignment8.mdwn @@ -1,39 +1,41 @@ -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. +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_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) *) - YOU SUPPLY THE DEFINITION + (* 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 + _____ + (* YOU SUPPLY THE DEFINITION *) let new_zipper (t : 'a tree) : 'a zipper = - {tree = Root; filler = t} + {level = 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 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 @@ -43,7 +45,9 @@ | 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 ;; @@ -60,7 +64,7 @@ ;; -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 continuations as arguments. Your assignment is to supply comments to the code, to explain what every significant piece is doing. +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; @@ -73,11 +77,17 @@ 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: @@ -90,7 +100,7 @@ * `(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 + * `(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 @@ -99,19 +109,19 @@ Here is the implementation: (define (lazy-flatten tree) - (letrec ([helper (lambda (tree tailk) + (letrec ([helper (lambda (tree tail-thunk) (cond [(pair? tree) - (helper (car tree) (lambda () (helper (cdr tree) tailk)))] - [else (cons tree tailk)]))]) - (helper tree (lambda () (list))))) + (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)) #t] + [(and (null? stream1) (null? stream2)) _____] [(and (pair? stream1) (pair? stream2)) (and (equal? (car stream1) (car stream2)) - (stream-equal? ((cdr stream1)) ((cdr stream2))))] + _____)] [else #f])) (define (same-fringe? tree1 tree2)