remove link to advanced from index
[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 pred = \n. isZero n 0 (length (tail (n (\p. makeList meh p) nil)))
40 in
41 let leq = \m n. isZero(n pred m) in
42 let eq = \m n. and (leq m n)(leq n m) in
43
44 eq 2 2 yes no
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
62 two lists have the
63 same length.  That is,
64
65      listLenEq mylist (makeList meh (makeList meh (makeList meh nil)))
66      ~~> true
67
68      listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
69
70
71 4. (Still easy) Now write the same function, but don't use the length
72 function.
73
74 5. In assignment 2, we discovered that version 3-type lists (the ones
75 that
76 work like Church numerals) made it much easier to define operations
77 like `map` and `filter`.  But now that we have recursion in our
78 toolbox,
79 reasonable map and filter functions for version 1 lists are within our
80 reach.  Give definitions for `map` and a `filter` for verson 1 type
81 lists.
82
83 #Computing with trees#
84
85 Linguists analyze natural language expressions into trees.  
86 We'll need trees in future weeks, and tree structures provide good
87 opportunities for learning how to write recursive functions.
88 Making use of the resources we have at the moment, we can approximate
89 trees as follows: instead of words, we'll use Church numerals.
90 Then a tree will be a (version 1 type) list in which each element is
91 itself a tree.  For simplicity, we'll adopt the convention that 
92 a tree of length 1 must contain a number as its only element.  
93 Then we have the following representations:
94
95 <pre>
96    (a)           (b)             (c)  
97     .
98    /|\            /\              /\
99   / | \          /\ 3            1 /\
100   1 2  3        1  2               2 3
101
102 [[1];[2];[3]]  [[[1];[2]];[3]]   [[1];[[2];[3]]]
103 </pre>
104
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
108 single daughter.
109
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
114 trees.
115
116 1.    Write a function that sums the number of leaves in a tree.
117
118 Expected behavior:
119
120 <pre>
121 let t1 = (makeList 1 nil) in
122 let t2 = (makeList 2 nil) in
123 let t3 = (makeList 3 nil) in
124 let t12 = (makeList t1 (makeList t2 nil)) in
125 let t23 = (makeList t2 (makeList t3 nil)) in
126 let ta = (makeList t1 t23) in
127 let tb = (makeList t12 t3) in
128 let tc = (makeList t1 (makeList t23 nil)) in
129
130 sum-leaves t1 ~~> 1
131 sum-leaves t2 ~~> 2
132 sum-leaves t3 ~~> 3
133 sum-leaves t12 ~~> 3
134 sum-leaves t23 ~~> 5
135 sum-leaves ta ~~> 6
136 sum-leaves tb ~~> 6
137 sum-leaves tc ~~> 6
138 </pre>
139
140 2.   Write a function that counts the number of leaves.
141