342896c2c429ee51d798d943352d415d682aa7a5
[lambda.git] / assignment3.mdwn
1 Assignment 3
2 ------------
3
4 Once again, the lambda evaluator will make working through this
5 assignment much faster and more secure.
6
7 *Writing recursive functions on version 1 style lists*
8
9 Recall that version 1 style lists are constructed like this (see
10 [[lists and numbers]]):
11
12 <pre>
13 ; booleans
14 let true = \x y. x in
15 let false = \x y. y in
16 let and = \l r. l (r true false) false in
17
18 ; version 1 lists
19 let makePair = \f s g. g f s in
20 let fst = true in
21 let snd = false in
22 let nil = makePair true meh in
23 let isNil = \x. x fst in
24 let makeList = \h t. makePair false (makePair h t) in
25 let head = \l. isNil l err (l snd fst) in
26 let tail = \l. isNil l err (l snd snd) in
27
28 ; a list of numbers to experiment on
29 let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in
30
31 ; a fixed-point combinator for defining recursive functions 
32 let Y = \f. (\h. f (h h)) (\h. f (h h)) in
33
34 ; church numerals
35 let isZero = \n. n (\x. false) true in
36 let succ = \n s z. s (n s z) in
37 let mult = \m n s. m (n s) in
38 let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in
39 let predecessor = \n. length (tail (n (\p. makeList meh p) nil)) in
40 let leq = ; (leq m n) will be true iff m is less than or equal to n
41   Y (\leq m n. isZero m true (isZero n false (leq (predecessor m)(predecessor n)))) in
42 let eq = \m n. and (leq m n)(leq n m) in
43
44 eq 3 3
45 </pre>
46
47
48 Then `length mylist` evaluates to 3.
49
50 1. What does `head (tail (tail mylist))` evaluate to?
51
52 2. Using the `length` function as a model, and using the predecessor
53 function, write a function that computes factorials.  (Recall that n!,
54 the factorial of n, is n times the factorial of n-1.)
55
56 Warning: my browser isn't able to compute factorials of numbers
57 greater than 2 (it does't provide enough resources for the JavaScript
58 interpreter; web pages are not supposed to be that computationally
59 intensive).
60
61 3. (Easy) Write a function `listLenEq` that returns true just in case two lists have the
62 same length.  That is,
63
64      listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) ~~> true
65
66      listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
67
68
69 4. (Still easy) Now write the same function, but don't use the length function (hint: use `leq` as a model).
70
71 5. In assignment 2, we discovered that version 3-type lists (the ones that
72 work like Church numerals) made it much easier to define operations
73 like map and filter.  But now that we have recursion in our toolbox,
74 reasonable map and filter functions for version 3 lists are within our
75 reach.  Give definitions for such a map and a filter.
76
77 6. Linguists analyze natural language expressions into trees.  
78 We'll need trees in future weeks, and tree structures provide good
79 opportunities for learning how to write recursive functions.
80 Making use of the resources we have at the moment, we can approximate
81 trees as follows: instead of words, we'll use Church numerals.
82 Then a tree will be a (version 1 type) list in which each element is
83 itself a tree.  For simplicity, we'll adopt the convention that 
84 a tree of length 1 must contain a number as its only element.  
85 Then we have the following representations:
86
87 <pre>
88    (a)           (b)             (c)  
89     .
90    /|\            /\              /\
91   / | \          /\ 3             1/\
92   1 2  3        1  2               2 3
93
94 [[1];[2];[3]]  [[[1];[2]];[3]]   [[1];[[2];[3]]]
95 </pre>
96
97 Limitations of this scheme include the following: there is no easy way
98 to label a constituent (typically a syntactic category, S or NP or VP,
99 etc.), and there is no way to represent a tree in which a mother has a
100 single daughter.
101
102 When processing a tree, you can test for whether the tree contains
103 only a numeral (in which case the tree is leaf node) by testing for
104 whether the length of the list is less than or equal to 1.  This will
105 be your base case for your recursive functions that operate on trees.
106
107 Write a function that sums the number of leaves in a tree.
108 Expected behavior:
109
110 <pre>
111
112 let t1 = (make-list 1 nil) in
113 let t2 = (make-list 2 nil) in
114 let t3 = (make-list 3 nil) in
115 let t12 = (make-list t1 (make-list t2 nil)) in
116 let t23 = (make-list t2 (make-list t3 nil)) in
117 let ta = (make-list t1 t23) in
118 let tb = (make-list t12 t3) in
119 let tc = (make-list t1 (make-list t23 nil)) in
120
121 count-leaves t1 ~~> 1
122 count-leaves t2 ~~> 2
123 count-leaves t3 ~~> 3
124 count-leaves t12 ~~> 3
125 count-leaves t23 ~~> 5
126 count-leaves ta ~~> 6
127 count-leaves tb ~~> 6
128 count-leaves tc ~~> 6
129 <pre>
130
131 Write a function that counts the number of leaves.
132
133
134
135
136 [The following should be correct, but won't run in my browser:
137
138 <pre>
139 let factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in
140
141 let reverse = 
142   Y (\rev l. isNil l nil 
143                    (isNil (tail l) l 
144                           (makeList (head (rev (tail l))) 
145                                     (rev (makeList (head l) 
146                                                    (rev (tail (rev (tail l))))))))) in
147
148 reverse (makeList 1 (makeList 2 (makeList 3 nil)))
149 </pre>
150
151 It may require more resources than my browser is willing to devote to
152 JavaScript.]
153
154 ; trees
155 let t1 = (makeList 1 nil) in
156 let t2 = (makeList 2 nil) in
157 let t3 = (makeList 3 nil) in
158 let t12 = (makeList t1 (makeList t2 nil)) in
159 let t23 = (makeList t2 (makeList t3 nil)) in
160 let ta = (makeList t1 t23) in
161 let tb = (makeList t12 t3) in
162 let tc = (makeList t1 (makeList t23 nil)) in