Assignment 3 ------------ Once again, the lambda evaluator will make working through this assignment much faster and more secure. *Writing recursive functions on version 1 style lists* Recall that version 1 style lists are constructed like this:
; booleans
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 fst = true in
let snd = false in
let nil = makePair true meh 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

; 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

; 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 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

eq 3 3

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: 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. (Easy) 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. (Still easy) Now write the same function, but don't use the length function (hint: use leq as a model). 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 3 lists are within our reach. Give definitions for such a map and a filter. 6. 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:
   (a)           (b)             (c)
.
/|\            /\              /\
/ | \          /\ 3             1/\
1 2  3        1  2               2 3

[;;]  [[;];]   [;[;]]

Limitations of this scheme include the following: there is no easy way to label a constituent (typically 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 trees. Write a function that sums the number of leaves in a tree. Expected behavior: let t1 = (make-list 1 nil) let t2 = (make-list 2 nil) let t3 = (make-list 3 nil) let t12 = (make-list t1 (make-list t2 nil)) let t23 = (make-list t2 (make-list t3 nil)) let ta = (make-list t1 t23) let tb = (make-list t12 t3) let tc = (make-list t1 (make-list t23 nil)) count-leaves t1 ~~> 1 count-leaves t2 ~~> 2 count-leaves t3 ~~> 3 count-leaves t12 ~~> 3 count-leaves t23 ~~> 5 count-leaves ta ~~> 6 count-leaves tb ~~> 6 count-leaves tc ~~> 6 Write a function that counts the number of leaves. [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

let reverse =
Y (\rev l. isNil l nil
(isNil (tail l) l