changes to offsite-reading

[lambda.git] / assignment3.mdwn

diff --git a/assignment3.mdwn b/assignment3.mdwn
index 71960dc..f93afd6 100644 (file)
--- a/assignment3.mdwn
+++ b/assignment3.mdwn
@@ -4,29 +4,94 @@ Assignment 3
 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.
 

-*Writing recursive functions on version 1 style lists*
+##Writing recursive functions on version 1 style lists##

 
 Recall that version 1 style lists are constructed like this:
 
 <pre>
 
 Recall that version 1 style lists are constructed like this:
 
 <pre>

+; booleans

 let true = \x y. x in
 let false = \x y. y in
 let true = \x y. x in
 let false = \x y. y in

+let and = \l r. l (r true false) false in
+
+; version 1 lists

 let makePair = \f s g. g f s in
 let makePair = \f s g. g f s in

-let nil = makePair true meh in
-let makeList = \h t. makePair false (makePair h t) in
-let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in

 let fst = true in
 let snd = false in
 let fst = true in
 let snd = false in

+let nil = makePair true meh in

 let isNil = \x. x fst in
 let isNil = \x. x fst in

+let makeList = \h t. makePair false (makePair h t) in

 let head = \l. isNil l err (l snd fst) in
 let tail = \l. isNil l err (l snd snd) in
 let head = \l. isNil l err (l snd fst) in
 let tail = \l. isNil l err (l snd snd) in

-let succ = \n s z. s (n s z) in
+
+; a list of numbers to experiment on
+let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in
+
+; a fixed-point combinator for defining recursive functions 

 let Y = \f. (\h. f (h h)) (\h. f (h h)) in
 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
+let mult = \m n s. m (n s) in

 let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in
 let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in

+let predecessor = \n. length (tail (n (\p. makeList meh p) nil)) in
+let leq = ; (leq m n) will be true iff m is less than or equal to n
+  Y (\leq m n. isZero m true (isZero n false (leq (predecessor m)(predecessor n)))) in
+let eq = \m n. and (leq m n)(leq n m) in

 
 

-length mylist
+eq 3 3

 </pre>
 
 </pre>
 

+

 Then `length mylist` evaluates to 3.
 
 Then `length mylist` evaluates to 3.
 

-What does `head (tail (tail mylist))` evaluate to?
+1. Warm-up: What does `head (tail (tail mylist))` evaluate to?
+
+2. Using the `length` function as a model, and using the predecessor
+function, write a function that computes factorials.  (Recall that n!,
+the factorial of n, is n times the factorial of n-1.)
+
+Warning: my browser isn't able to compute factorials of numbers
+greater than 2 (it does't provide enough resources for the JavaScript
+interpreter; web pages are not supposed to be that computationally
+intensive).
+
+
+3. Write a function `listLenEq` that returns true just in case two lists have the
+same length.  That is,
+
+     listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) ~~> true
+
+     listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
+
+4. Now write the same function, but don't use the length function (hint: use `leq` as a model).
+
+##Trees##
+
+Since we'll be working with linguistic objects, let's approximate
+trees as follows: a tree is a version 1 list
+a Church number is a tree, and 
+if A and B are trees, then (make-pair A B) is a tree.
+
+
+
+
+[The following should be correct, but won't run in my browser:
+
+let factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in
+
+<pre>
+let reverse = 
+  Y (\rev l. isNil l nil 
+                   (isNil (tail l) l 
+                          (makeList (head (rev (tail l))) 
+                                    (rev (makeList (head l) 
+                                                   (rev (tail (rev (tail l))))))))) in
+
+reverse (makeList 1 (makeList 2 (makeList 3 nil)))
+</pre>
+
+It may require more resources than my browser is willing to devote to
+JavaScript.]
+