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 (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 ; version 1 lists let make_pair = \f s g. g f s in let fst = true in let snd = false in let empty = make_pair true junk in let isempty = \x. x fst 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 ; 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 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 leq = \m n. iszero(n pred m) in let eq = \m n. and (leq m n)(leq n m) 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 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:
(a) (b) (c) . /|\ /\ /\ / | \ /\ 3 1 /\ 1 2 3 1 2 2 3 [[1];[2];[3]] [[[1];[2]];[3]] [[1];[[2];[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.