4 Erratum corrected 11PM Sun 3 Oct: the following line
6 let tb = (make_list t12 (make_list t3 empty)) in
10 let tb = (make_list t12 t3) in
12 This has been corrected below, and in the preloaded evaluator for
13 working on assignment 3.
17 Once again, the lambda evaluator will make working through this
18 assignment much faster and more secure.
20 #Writing recursive functions on version 1 style lists#
22 Recall that version 1 style lists are constructed like this (see
23 [[lists and numbers]]):
27 let false = \x y. y in
28 let and = \l r. l (r true false) false in
30 let make_pair = \f s g. g f s in
32 let get_snd = false in
33 let empty = make_pair true junk in
34 let isempty = \x. x get_fst in
35 let make_list = \h t. make_pair false (make_pair h t) in
36 let head = \l. isempty l err (l get_snd get_fst) in
37 let tail = \l. isempty l err (l get_snd get_snd) in
39 ; a list of numbers to experiment on
40 let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
43 let iszero = \n. n (\x. false) true in
44 let succ = \n s z. s (n s z) in
45 let mul = \m n s. m (n s) in
46 let pred = (\shift n. n shift (make\_pair 0 0) get\_snd) (\p. p (\x y. make\_pair (succ x) x)) in
47 let leq = \m n. iszero(n pred m) in
48 let eq = \m n. and (leq m n)(leq n m) in
50 ; a fixed-point combinator for defining recursive functions
51 let Y = \f. (\h. f (h h)) (\h. f (h h)) in
52 let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
57 Then `length mylist` evaluates to 3.
59 1. What does `head (tail (tail mylist))` evaluate to?
61 2. Using the `length` function as a model, and using the predecessor
62 function, write a function that computes factorials. (Recall that n!,
63 the factorial of n, is n times the factorial of n-1.)
65 Warning: it takes a long time for my browser to compute factorials larger than 4!
67 3. (Easy) Write a function `equal_length` that returns true just in case
68 two lists have the same length. That is,
70 equal_length mylist (make_list junk (make_list junk (make_list junk empty))) ~~> true
72 equal_length mylist (make_list junk (make_list junk empty))) ~~> false
75 4. (Still easy) Now write the same function, but don't use the length
78 5. In assignment 2, we discovered that version 3-type lists (the ones
80 work like Church numerals) made it much easier to define operations
81 like `map` and `filter`. But now that we have recursion in our
83 reasonable map and filter functions for version 1 lists are within our
84 reach. Give definitions for `map` and a `filter` for verson 1 type
87 #Computing with trees#
89 Linguists analyze natural language expressions into trees.
91 We'll need trees in future weeks, and tree structures provide good
92 opportunities for learning how to write recursive functions.
93 Making use of the resources we have at the moment, we can approximate
94 trees as follows: instead of words, we'll use Church numerals.
95 Then a tree will be a (version 1 type) list in which each element is
96 itself a tree. For simplicity, we'll adopt the convention that
97 a tree of length 1 must contain a number as its only element.
99 Then we have the following representations:
108 [[1];[2];[3]] [[[1];[2]];[3]] [[1];[[2];[3]]]
111 Limitations of this scheme include the following: there is no easy way
112 to label a constituent with a syntactic category (S or NP or VP,
113 etc.), and there is no way to represent a tree in which a mother has a
116 When processing a tree, you can test for whether the tree contains
117 only a numeral (in which case the tree is leaf node) by testing for
118 whether the length of the list is less than or equal to 1. This will
119 be your base case for your recursive functions that operate on these
123 <LI>Write a function that sums the values at the leaves in a tree.
127 let t1 = (make_list 1 empty) in
128 let t2 = (make_list 2 empty) in
129 let t3 = (make_list 3 empty) in
130 let t12 = (make_list t1 (make_list t2 empty)) in
131 let t23 = (make_list t2 (make_list t3 empty)) in
132 let ta = (make_list t1 t23) in
133 let tb = (make_list t12 (make_list t3 empty)) in
134 let tc = (make_list t1 (make_list t23 empty)) in
146 <LI>Write a function that counts the number of leaves.