Merge branch 'pryor'

[lambda.git] / assignment3.mdwn

diff --git a/assignment3.mdwn b/assignment3.mdwn
index 71960dc..e240b73 100644 (file)
--- a/assignment3.mdwn
+++ b/assignment3.mdwn
@@ -1,32 +1,151 @@
 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.
 

-*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 (see
+[[lists and numbers]]):
+
+       ; booleans
+       let true = \x y. x in
+       let false = \x y. y in
+       let and = \l r. l (r true false) false in
+
+       let make_pair = \f s g. g f s in
+       let get_fst = true in
+       let get_snd = false in
+       let empty = make_pair true junk in
+       let isempty = \x. x get_fst in
+       let make_list = \h t. make_pair false (make_pair h t) 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
+       
+       ; church numerals
+       let iszero = \n. n (\x. false) true in
+       let succ = \n s z. s (n s z) 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
+       
+       ; 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
+
+
+Then `length mylist` evaluates to 3.
+
+1. 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: 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,
+
+               equal_length mylist (make_list junk (make_list junk (make_list junk empty))) ~~> true

 
 

-Recall that version 1 style lists are constructed like this:
+               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
+function.
+
+5. In assignment 2, we discovered that version 3-type lists (the ones
+that
+work like Church numerals) made it much easier to define operations
+like `map` and `filter`.  But now that we have recursion in our
+toolbox,
+reasonable map and filter functions for version 1 lists are within our
+reach.  Give definitions for `map` and a `filter` for verson 1 type
+lists.
+
+#Computing with trees#
+
+Linguists analyze natural language expressions into trees.
+
+We'll need trees in future weeks, and tree structures provide good
+opportunities for learning how to write recursive functions.
+Making use of the resources we have at the moment, we can approximate
+trees as follows: instead of words, we'll use Church numerals.
+Then a tree will be a (version 1 type) list in which each element is
+itself a tree.  For simplicity, we'll adopt the convention that
+a tree of length 1 must contain a number as its only element.
+
+Then we have the following representations:

 
 <pre>
 
 <pre>

-let true = \x y. x in
-let false = \x y. y 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 isNil = \x. x fst 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
-let Y = \f. (\h. f (h h)) (\h. f (h h)) in
-let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in
-
-length mylist
+   (a)           (b)             (c)
+    .
+   /|\            /\              /\
+  / | \          /\ 3            1 /\
+  1 2  3        1  2               2 3
+
+[[1];[2];[3]]  [[[1];[2]];[3]]   [[1];[[2];[3]]]

 </pre>
 
 </pre>
 

-Then `length mylist` evaluates to 3.
+Limitations of this scheme include the following: there is no easy way
+to label a constituent with a syntactic category (S or NP or VP,
+etc.), and there is no way to represent a tree in which a mother has a
+single daughter.
+
+When processing a tree, you can test for whether the tree contains
+only a numeral (in which case the tree is leaf node) by testing for
+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.
+
+<OL start=6>
+<LI>Write a function that sums the values at the leaves in a tree.
+
+Expected behavior:
+
+       let t1 = (make_list 1 empty) in
+       let t2 = (make_list 2 empty) in
+       let t3 = (make_list 3 empty) 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 (make_list t3 empty)) in
+       let tc = (make_list t1 (make_list t23 empty)) in
+
+       sum-leaves t1 ~~> 1
+       sum-leaves t2 ~~> 2
+       sum-leaves t3 ~~> 3
+       sum-leaves t12 ~~> 3
+       sum-leaves t23 ~~> 5
+       sum-leaves ta ~~> 6
+       sum-leaves tb ~~> 6
+       sum-leaves tc ~~> 6
+
+
+<LI>Write a function that counts the number of leaves.
+
+</OL>

 
 

-What does `head (tail (tail mylist))` evaluate to?