c4d999275defbca34ccbaaa9c397ca7186491b5e
1 Assignment 3
2 ------------
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]]):
12         ; booleans
13         let true = \x y. x in
14         let false = \x y. y in
15         let and = \l r. l (r true false) false in
17         ; version 1 lists
18         let make_pair = \f s g. g f s in
19         let fst = true in
20         let snd = false 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
33         ; church numerals
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)))
39         in
40         let leq = \m n. iszero(n pred m) in
41         let eq = \m n. and (leq m n)(leq n m) in
43         eq 2 2 yes no
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: it takes a long time for my browser to compute factorials larger than 4!
56 3. (Easy) Write a function `equal_length` that returns true just in case
57 two lists have the same length.  That is,
59      equal_length mylist (make_list junk (make_list junk (make_list junk empty)))
60      ~~> true
62      equal_length mylist (make_list junk (make_list junk empty))) ~~> false
65 4. (Still easy) Now write the same function, but don't use the length
66 function.
68 5. In assignment 2, we discovered that version 3-type lists (the ones
69 that
70 work like Church numerals) made it much easier to define operations
71 like `map` and `filter`.  But now that we have recursion in our
72 toolbox,
73 reasonable map and filter functions for version 1 lists are within our
74 reach.  Give definitions for `map` and a `filter` for verson 1 type
75 lists.
77 #Computing with trees#
79 Linguists analyze natural language expressions into trees.
81 We'll need trees in future weeks, and tree structures provide good
82 opportunities for learning how to write recursive functions.
83 Making use of the resources we have at the moment, we can approximate
84 trees as follows: instead of words, we'll use Church numerals.
85 Then a tree will be a (version 1 type) list in which each element is
86 itself a tree.  For simplicity, we'll adopt the convention that
87 a tree of length 1 must contain a number as its only element.
89 Then we have the following representations:
91 <pre>
92    (a)           (b)             (c)
93     .
94    /|\            /\              /\
95   / | \          /\ 3            1 /\
96   1 2  3        1  2               2 3
98 [;;]  [[;];]   [;[;]]
99 </pre>
101 Limitations of this scheme include the following: there is no easy way
102 to label a constituent with a syntactic category (S or NP or VP,
103 etc.), and there is no way to represent a tree in which a mother has a
104 single daughter.
106 When processing a tree, you can test for whether the tree contains
107 only a numeral (in which case the tree is leaf node) by testing for
108 whether the length of the list is less than or equal to 1.  This will
109 be your base case for your recursive functions that operate on these
110 trees.
112 1.    Write a function that sums the number of leaves in a tree.
114 Expected behavior:
116         let t1 = (make_list 1 empty) in
117         let t2 = (make_list 2 empty) in
118         let t3 = (make_list 3 empty) in
119         let t12 = (make_list t1 (make_list t2 empty)) in
120         let t23 = (make_list t2 (make_list t3 empty)) in
121         let ta = (make_list t1 t23) in
122         let tb = (make_list t12 t3) in
123         let tc = (make_list t1 (make_list t23 empty)) in
125         sum-leaves t1 ~~> 1
126         sum-leaves t2 ~~> 2
127         sum-leaves t3 ~~> 3
128         sum-leaves t12 ~~> 3
129         sum-leaves t23 ~~> 5
130         sum-leaves ta ~~> 6
131         sum-leaves tb ~~> 6
132         sum-leaves tc ~~> 6
135 2.   Write a function that counts the number of leaves.