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
| 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
;;
;;
-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.
+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 "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;
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 _____ tailk)))]
- [else (cons tree tailk)]))])
+ (helper (car tree) (lambda () (helper _____ tail-thunk)))]
+ [else (cons tree tail-thunk)]))])
(helper tree (lambda () _____))))
(define (stream-equal? stream1 stream2)