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