cleanup
[lambda.git] / assignment8.mdwn
1 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.
2
3                 type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree)
4
5                 type 'a starred_level = Root | Starring_Left of 'a starred_nonroot | Starring_Right of 'a starred_nonroot
6                 and 'a starred_nonroot = { parent : 'a starred_level; sibling: 'a tree };;
7
8                 type 'a zipper = { level : 'a starred_level; filler: 'a tree };;
9
10                 let rec move_botleft (z : 'a zipper) : 'a zipper =
11                         (* returns z if the targetted node in z has no children *)
12                         (* else returns move_botleft (zipper which results from moving down from z to the leftmost child) *)
13                         _____
14                         (* YOU SUPPLY THE DEFINITION *)
15
16
17                 let rec move_right_or_up (z : 'a zipper) : 'a zipper option =
18                         (* if it's possible to move right in z, returns Some (the result of doing so) *)
19                         (* else if it's not possible to move any further up in z, returns None *)
20                         (* else returns move_right_or_up (result of moving up in z) *)
21                         _____
22                         (* YOU SUPPLY THE DEFINITION *)
23
24
25                 let new_zipper (t : 'a tree) : 'a zipper =
26                         {level = Root; filler = t}
27                         ;;
28
29          
30
31                 let make_fringe_enumerator (t: 'a tree) =
32                         (* create a zipper targetting the botleft of t *)
33                         let zbotleft = move_botleft (new_zipper t)
34                         (* create a refcell initially pointing to zbotleft *)
35                         in let zcell = ref (Some zbotleft)
36                         (* construct the next_leaf function *)
37                         in let next_leaf () : 'a option =
38                                 match !zcell with
39                                 | Some z -> (
40                                         (* extract label of currently-targetted leaf *)
41                                         let Leaf current = z.filler
42                                         (* update zcell to point to next leaf, if there is one *)
43                                         in let () = zcell := match move_right_or_up z with
44                                                 | None -> None
45                                                 | Some z' -> Some (move_botleft z')
46                                         (* return saved label *)
47                                         in Some current
48                                     )
49                                 | None -> (* we've finished enumerating the fringe *)
50                                         None
51                         (* return the next_leaf function *)
52                         in next_leaf
53                         ;;
54
55                 let same_fringe (t1 : 'a tree) (t2 : 'a tree) : bool =
56                         let next1 = make_fringe_enumerator t1
57                         in let next2 = make_fringe_enumerator t2
58                         in let rec loop () : bool =
59                                 match next1 (), next2 () with
60                                 | Some a, Some b when a = b -> loop ()
61                                 | None, None -> true
62                                 | _ -> false
63                         in loop ()
64                         ;;
65
66
67 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.
68
69         This code uses Scheme's `cond` construct. That works like this;
70
71                 (cond
72                         ((test1 argument argument) result1)
73                         ((test2 argument argument) result2)
74                         ((test3 argument argument) result3)
75                         (else result4))
76
77         is equivalent to:
78
79                 (if (test1 argument argument)
80                         ; then
81                         result1
82                         ; else
83                         (if (test2 argument argument)
84                                 ; then
85                                 result2
86                                 ; else
87                                 (if (test3 argument argument)
88                                         ; then
89                                         result3
90                                         ; else
91                                         result4)))
92
93         Some other Scheme details:
94
95         *       `#t` is true and `#f` is false
96         *       `(lambda () ...)` constructs a thunk
97         *       there is no difference in meaning between `[...]` and `(...)`; we just sometimes use the square brackets for clarity
98         *       `'(1 . 2)` and `(cons 1 2)` are pairs (the same pair)
99         *       `(list)` and `'()` both evaluate to the empty list
100         *       `(null? lst)` tests whether `lst` is the empty list
101         *       non-empty lists are implemented as pairs whose second member is a list
102         *       `'()` `'(1)` `'(1 2)` `'(1 2 3)` are all lists
103         *       `(list)` `(list 1)` `(list 1 2)` `(list 1 2 3)` are the same lists as the preceding
104         *       `'(1 2 3)` and `(cons 1 '(2 3))` are both pairs and lists (the same list)
105         *       `(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
106         *       `(car lst)` extracts the first member of a pair / head of a list
107         *       `(cdr lst)` extracts the second member of a pair / tail of a list
108
109         Here is the implementation:
110
111                 (define (lazy-flatten tree)
112                   (letrec ([helper (lambda (tree tail-thunk)
113                                   (cond
114                                     [(pair? tree)
115                                       (helper (car tree) (lambda () (helper _____ tail-thunk)))]
116                                     [else (cons tree tail-thunk)]))])
117                     (helper tree (lambda () _____))))
118                 
119                 (define (stream-equal? stream1 stream2)
120                   (cond
121                     [(and (null? stream1) (null? stream2)) _____]
122                     [(and (pair? stream1) (pair? stream2))
123                      (and (equal? (car stream1) (car stream2))
124                           _____)]
125                     [else #f]))
126                 
127                 (define (same-fringe? tree1 tree2)
128                   (stream-equal? (lazy-flatten tree1) (lazy-flatten tree2)))
129                 
130                 (define tree1 '(((1 . 2) . (3 . 4)) . (5 . 6)))
131                 (define tree2 '(1 . (((2 . 3) . (4 . 5)) . 6)))
132                 
133                 (same-fringe? tree1 tree2)
134
135