----
-
-
-Finally, we can use a mutable reference cell to define a function that enumerates a tree's fringe until it's exhausted:
-
- let make_fringe_enumerator (t: 'a tree) =
- (* create a zipper focusing 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-focused leaf *)
- let Leaf current = z.in_focus
- (* 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
- ;;
-
-
-Using these fringe enumerators, we can write our `same_fringe` function like this:
-
- 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 ()
- ;;
-
-The auxiliary `loop` function will keep calling itself recursively until a difference in the fringes has manifested itself---either because one fringe is exhausted before the other, or because the next leaves in the two fringes have different labels. If we get to the end of both fringes at the same time (`next1 (), next2 ()` matches the pattern `None, None`) then we've established that the trees do have the same fringe.
-
-
-
----
-
-4. 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 or reminders:
-
- * `#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:
+Okay, now armed with the idea of a stream, let's use a Scheme version of them to handle the same-fringe problem. This code is 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 or reminders:
+
+* `#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
+
+<!-- -->
+
+4. Here is the Scheme code handling the same-fringe problem. You should fill in the blanks: