-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)
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}
;;
+
+
let make_fringe_enumerator (t: 'a tree) =
(* create a zipper targetting the root of t *)
let zstart = new_zipper t
;;
-2. 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 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 <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 continuations (`tailk`s) as arguments. 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;
* `(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
(letrec ([helper (lambda (tree tailk)
(cond
[(pair? tree)
- (helper (car tree) (lambda () (helper (cdr tree) tailk)))]
+ (helper (car tree) (lambda () (helper _____ tailk)))]
[else (cons tree tailk)]))])
- (helper tree (lambda () (list)))))
+ (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)