assign7 tweak
[lambda.git] / assignment3.mdwn
index c4d9992..e240b73 100644 (file)
@@ -1,6 +1,19 @@
 Assignment 3
 ------------
 
 Assignment 3
 ------------
 
+Erratum corrected 11PM Sun 3 Oct: the following line
+
+       let tb = (make_list t12 (make_list t3 empty)) in
+
+originally read 
+
+       let tb = (make_list t12 t3) in
+
+This has been corrected below, and in the preloaded evaluator for 
+working on assignment 3, available here: [[assignment 3 evaluator]].
+
+<hr>
+
 Once again, the lambda evaluator will make working through this
 assignment much faster and more secure.
 
 Once again, the lambda evaluator will make working through this
 assignment much faster and more secure.
 
@@ -14,32 +27,32 @@ Recall that version 1 style lists are constructed like this (see
        let false = \x y. y in
        let and = \l r. l (r true false) false in
 
        let false = \x y. y in
        let and = \l r. l (r true false) false in
 
-       ; version 1 lists
        let make_pair = \f s g. g f s in
        let make_pair = \f s g. g f s in
-       let fst = true in
-       let snd = false in
+       let get_fst = true in
+       let get_snd = false in
        let empty = make_pair true junk in
        let empty = make_pair true junk in
-       let isempty = \x. x fst in
+       let isempty = \x. x get_fst in
        let make_list = \h t. make_pair false (make_pair h t) in
        let make_list = \h t. make_pair false (make_pair h t) in
-       let head = \l. isempty l err (l snd fst) in
-       let tail = \l. isempty l err (l snd snd) in
-
+       let head = \l. isempty l err (l get_snd get_fst) in
+       let tail = \l. isempty l err (l get_snd get_snd) in
+       
        ; a list of numbers to experiment on
        let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
        ; a list of numbers to experiment on
        let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
-
-       ; a fixed-point combinator for defining recursive functions
-       let Y = \f. (\h. f (h h)) (\h. f (h h)) in
-
+       
        ; church numerals
        let iszero = \n. n (\x. false) true in
        let succ = \n s z. s (n s z) in
        ; church numerals
        let iszero = \n. n (\x. false) true in
        let succ = \n s z. s (n s z) in
-       let mult = \m n s. m (n s) in
-       let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
-       let pred = \n. iszero n 0 (length (tail (n (\p. make_list junk p) empty)))
-       in
+       let add = \l r. l succ r in
+       let mul = \m n s. m (n s) in
+       let pred = (\shift n. n shift (make\_pair 0 0) get\_snd) (\p. p (\x y. make\_pair (succ x) x)) in
        let leq = \m n. iszero(n pred m) in
        let eq = \m n. and (leq m n)(leq n m) in
        let leq = \m n. iszero(n pred m) in
        let eq = \m n. and (leq m n)(leq n m) in
-
+       
+       ; a fixed-point combinator for defining recursive functions
+       let Y = \f. (\h. f (h h)) (\h. f (h h)) in
+       let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
+       let fold = Y (\f l g z. isempty l z (g (head l)(f (tail l) g z))) in
+       
        eq 2 2 yes no
 
 
        eq 2 2 yes no
 
 
@@ -51,15 +64,14 @@ Then `length mylist` evaluates to 3.
 function, write a function that computes factorials.  (Recall that n!,
 the factorial of n, is n times the factorial of n-1.)
 
 function, write a function that computes factorials.  (Recall that n!,
 the factorial of n, is n times the factorial of n-1.)
 
-Warning: it takes a long time for my browser to compute factorials larger than 4!
+       Warning: it takes a long time for my browser to compute factorials larger than 4!
 
 3. (Easy) Write a function `equal_length` that returns true just in case
 two lists have the same length.  That is,
 
 
 3. (Easy) Write a function `equal_length` that returns true just in case
 two lists have the same length.  That is,
 
-     equal_length mylist (make_list junk (make_list junk (make_list junk empty)))
-     ~~> true
+               equal_length mylist (make_list junk (make_list junk (make_list junk empty))) ~~> true
 
 
-     equal_length mylist (make_list junk (make_list junk empty))) ~~> false
+               equal_length mylist (make_list junk (make_list junk empty))) ~~> false
 
 
 4. (Still easy) Now write the same function, but don't use the length
 
 
 4. (Still easy) Now write the same function, but don't use the length
@@ -109,7 +121,8 @@ whether the length of the list is less than or equal to 1.  This will
 be your base case for your recursive functions that operate on these
 trees.
 
 be your base case for your recursive functions that operate on these
 trees.
 
-1.    Write a function that sums the number of leaves in a tree.
+<OL start=6>
+<LI>Write a function that sums the values at the leaves in a tree.
 
 Expected behavior:
 
 
 Expected behavior:
 
@@ -119,7 +132,7 @@ Expected behavior:
        let t12 = (make_list t1 (make_list t2 empty)) in
        let t23 = (make_list t2 (make_list t3 empty)) in
        let ta = (make_list t1 t23) in
        let t12 = (make_list t1 (make_list t2 empty)) in
        let t23 = (make_list t2 (make_list t3 empty)) in
        let ta = (make_list t1 t23) in
-       let tb = (make_list t12 t3) in
+       let tb = (make_list t12 (make_list t3 empty)) in
        let tc = (make_list t1 (make_list t23 empty)) in
 
        sum-leaves t1 ~~> 1
        let tc = (make_list t1 (make_list t23 empty)) in
 
        sum-leaves t1 ~~> 1
@@ -132,5 +145,7 @@ Expected behavior:
        sum-leaves tc ~~> 6
 
 
        sum-leaves tc ~~> 6
 
 
-2.   Write a function that counts the number of leaves.
+<LI>Write a function that counts the number of leaves.
+
+</OL>