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