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 () ;;`

Here's another implementation of the same-fringe function, in Scheme. It's taken from http://c2.com/cgi/wiki?SameFringeProblem. 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)`