4 Once again, the lambda evaluator will make working through this
5 assignment much faster and more secure.
7 #Writing recursive functions on version 1 style lists#
9 Recall that version 1 style lists are constructed like this (see
10 [[lists and numbers]]):
14 let false = \x y. y in
15 let and = \l r. l (r true false) false in
18 let make_pair = \f s g. g f s in
21 let empty = make_pair true junk in
22 let isempty = \x. x fst in
23 let make_list = \h t. make_pair false (make_pair h t) in
24 let head = \l. isempty l err (l snd fst) in
25 let tail = \l. isempty l err (l snd snd) in
27 ; a list of numbers to experiment on
28 let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
30 ; a fixed-point combinator for defining recursive functions
31 let Y = \f. (\h. f (h h)) (\h. f (h h)) in
34 let iszero = \n. n (\x. false) true in
35 let succ = \n s z. s (n s z) in
36 let mult = \m n s. m (n s) in
37 let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
38 let pred = \n. iszero n 0 (length (tail (n (\p. make_list junk p) empty)))
40 let leq = \m n. iszero(n pred m) in
41 let eq = \m n. and (leq m n)(leq n m) in
46 Then `length mylist` evaluates to 3.
48 1. What does `head (tail (tail mylist))` evaluate to?
50 2. Using the `length` function as a model, and using the predecessor
51 function, write a function that computes factorials. (Recall that n!,
52 the factorial of n, is n times the factorial of n-1.)
54 Warning: my browser isn't able to compute factorials of numbers
55 greater than 2 (it does't provide enough resources for the JavaScript
56 interpreter; web pages are not supposed to be that computationally
59 3. (Easy) Write a function `listLenEq` that returns true just in case
63 listLenEq mylist (make_list junk (make_list junk (make_list junk empty)))
66 listLenEq mylist (make_list junk (make_list junk empty))) ~~> false
69 4. (Still easy) Now write the same function, but don't use the length
72 5. In assignment 2, we discovered that version 3-type lists (the ones
74 work like Church numerals) made it much easier to define operations
75 like `map` and `filter`. But now that we have recursion in our
77 reasonable map and filter functions for version 1 lists are within our
78 reach. Give definitions for `map` and a `filter` for verson 1 type
81 #Computing with trees#
83 Linguists analyze natural language expressions into trees.
85 We'll need trees in future weeks, and tree structures provide good
86 opportunities for learning how to write recursive functions.
87 Making use of the resources we have at the moment, we can approximate
88 trees as follows: instead of words, we'll use Church numerals.
89 Then a tree will be a (version 1 type) list in which each element is
90 itself a tree. For simplicity, we'll adopt the convention that
91 a tree of length 1 must contain a number as its only element.
93 Then we have the following representations:
102 [[1];[2];[3]] [[[1];[2]];[3]] [[1];[[2];[3]]]
105 Limitations of this scheme include the following: there is no easy way
106 to label a constituent with a syntactic category (S or NP or VP,
107 etc.), and there is no way to represent a tree in which a mother has a
110 When processing a tree, you can test for whether the tree contains
111 only a numeral (in which case the tree is leaf node) by testing for
112 whether the length of the list is less than or equal to 1. This will
113 be your base case for your recursive functions that operate on these
116 1. Write a function that sums the number of leaves in a tree.
120 let t1 = (make_list 1 empty) in
121 let t2 = (make_list 2 empty) in
122 let t3 = (make_list 3 empty) in
123 let t12 = (make_list t1 (make_list t2 empty)) in
124 let t23 = (make_list t2 (make_list t3 empty)) in
125 let ta = (make_list t1 t23) in
126 let tb = (make_list t12 t3) in
127 let tc = (make_list t1 (make_list t23 empty)) in
139 2. Write a function that counts the number of leaves.