tweak monads-lib, migrate to T2

[lambda.git] / assignment3.mdwn

diff --git a/assignment3.mdwn b/assignment3.mdwn
index 8c22dfa..e240b73 100644 (file)
--- a/assignment3.mdwn
+++ b/assignment3.mdwn
@@ -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
 
 


@@ -109,7 +122,7 @@ be your base case for your recursive functions that operate on these
 trees.
 
 <OL start=6>
 trees.
 
 <OL start=6>

-<LI>Write a function that sums the number of leaves in a tree.
+<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