X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment8.mdwn;h=f09556f075c06c75c835b94cbc2cb7ff1fedf6f1;hp=abc14d08b87337bbaa56a1d025157714a0c6949a;hb=HEAD;hpb=48a42d03d6e2562628e1ab9cc7e134cc9bcf4294

diff --git a/assignment8.mdwn b/assignment8.mdwn
deleted file mode 100644
index abc14d08..00000000
--- a/assignment8.mdwn
+++ /dev/null
@@ -1,124 +0,0 @@
-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.
-
-		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 };;
-
-		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
-
-
-		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
-
-
-		let new_zipper (t : 'a tree) : 'a zipper =
-			{tree = 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 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
-					(* 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
-				)
-			(* return the next_leaf function *)
-			in next_leaf
-			;;
-
-		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 ()
-			;;
-
-
-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.
-
-	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)
-			result1
-			(if (test2 argument argument)
-				result2
-				(if (test3 argument argument)
-					result3
-					result4)))
-
-	Some other Scheme details:
-
-	*	`#t` is true and `#f` is false
-	*	`'(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)` `(list1)` `(list 1 2)` `(list 1 2 3)` are the same lists
-	*	`'(1 2 3)` and `(cons 1 '(2 3))` are pairs that are also 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
-	*	`(lambda () ...)` constructs a thunk
-
-	Here is the implementation:
-
-		(define (lazy-flatten tree)
-		  (letrec ([helper (lambda (tree tailk)
-		                  (cond
-		                    [(pair? tree)
-		                      (helper (car tree) (lambda () (helper (cdr tree) tailk)))]
-		                    [else (cons tree tailk)]))])
-		    (helper tree (lambda () (list)))))
-		
-		(define (stream-equal? stream1 stream2)
-		  (cond
-		    [(and (null? stream1) (null? stream2)) #t]
-		    [(and (pair? stream1) (pair? stream2))
-		     (and (equal? (car stream1) (car stream2))
-		          (stream-equal? ((cdr stream1)) ((cdr 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)
-
-