arithmetic -> lambda_library

[lambda.git] / assignment3.mdwn

diff --git a/assignment3.mdwn b/assignment3.mdwn
index 013bc3c..6f4f3f6 100644 (file)
--- a/assignment3.mdwn
+++ b/assignment3.mdwn
@@ -4,9 +4,10 @@ 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:
+Recall that version 1 style lists are constructed like this (see
+[[lists and numbers]]):

 
 <pre>
 ; booleans
 
 <pre>
 ; booleans


@@ -35,12 +36,12 @@ 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 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 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 pred = \n. isZero n 0 (length (tail (n (\p. makeList meh p) nil)))
+in
+let leq = \m n. isZero(n pred m) in

 let eq = \m n. and (leq m n)(leq n m) in
 
 let eq = \m n. and (leq m n)(leq n m) in
 

-eq 3 3
+eq 2 2 yes no

 </pre>
 
 
 </pre>
 
 


@@ -57,35 +58,84 @@ greater than 2 (it does't provide enough resources for the JavaScript
 interpreter; web pages are not supposed to be that computationally
 intensive).
 
 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
+3. (Easy) Write a function `listLenEq` that returns true just in case
+two lists have the

 same length.  That is,
 
 same length.  That is,
 

-     listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) ~~> true
+     listLenEq mylist (makeList meh (makeList meh (makeList meh nil)))
+     ~~> true

 
      listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
 
 
 
      listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
 
 

-4. Now write the same function (true iff two lists have the same
-length) but don't use the length function (hint: use `leq` as a model).
+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>
+   (a)           (b)             (c)  
+    .
+   /|\            /\              /\
+  / | \          /\ 3            1 /\
+  1 2  3        1  2               2 3
+
+[[1];[2];[3]]  [[[1];[2]];[3]]   [[1];[[2];[3]]]
+</pre>
+
+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.

 
 

-   That is, (makeList 1 (makeList 2 (makeList 3 nil))) 
+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.

 
 

-[The following should be correct, but won't run in my browser:
+1.    Write a function that sums the number of leaves in a tree.

 
 

-let factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in
+Expected behavior:

 
 <pre>
 
 <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)))
+let t1 = (makeList 1 nil) in
+let t2 = (makeList 2 nil) in
+let t3 = (makeList 3 nil) in
+let t12 = (makeList t1 (makeList t2 nil)) in
+let t23 = (makeList t2 (makeList t3 nil)) in
+let ta = (makeList t1 t23) in
+let tb = (makeList t12 t3) in
+let tc = (makeList t1 (makeList t23 nil)) 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

 </pre>
 
 </pre>
 

-It may require more resources than my browser is willing to devote to
-JavaScript.]
+2.   Write a function that counts the number of leaves.