add plotkin link
[lambda.git] / assignment8.mdwn
index 547db8e..f09556f 100644 (file)
@@ -1,39 +1,41 @@
-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)
 
-               type 'a starred_tree = Root | Starring_Left of 'a starred_pair | Starring_Right of 'a starred_pair
-               and 'a starred_pair = { parent : 'a starred_tree; sibling: 'a tree }
-               and 'a zipper = { tree : 'a starred_tree; filler: '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 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}
+                       {level = Root; filler = t}
                        ;;
 
+        
+
                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
@@ -43,7 +45,9 @@
                                                | 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
                        ;;
                        in loop ()
                        ;;
 
+
+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;
+
+               (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)
+
+