X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment8.mdwn;h=495ef2f7218b10182b4e955b8d606dae4dea9c70;hp=547db8eda795b39b81e253edbc6a7da571a866ce;hb=b0ae43400b808fc96a9762d25868d6517e904a48;hpb=b7801991967a3ca88aaa238169eec3a63d916bcb

diff --git a/assignment8.mdwn b/assignment8.mdwn
index 547db8ed..495ef2f7 100644
--- a/assignment8.mdwn
+++ b/assignment8.mdwn
@@ -1,4 +1,4 @@
-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)
 
@@ -8,21 +8,25 @@
 
 		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}
 			;;
 
+	 
+
 		let make_fringe_enumerator (t: 'a tree) =
 			(* create a zipper targetting the root of t *)
 			let zstart = new_zipper t
@@ -59,3 +63,73 @@
 			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 (`tailk`s) as arguments. 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 tailk)
+		                  (cond
+		                    [(pair? tree)
+		                      (helper (car tree) (lambda () (helper _____ tailk)))]
+		                    [else (cons tree tailk)]))])
+		    (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)
+
+