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         ; 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 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
  26
  27         ; a list of numbers to experiment on
  28         let mylist = make_list 1 (make_list 2 (make_list 3 empty)) 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. 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
  42
  43         eq 2 2 yes no
  44
  45
  46 Then `length mylist` evaluates to 3.
  47
  48 1. What does `head (tail (tail mylist))` evaluate to?
  49
  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.)
  53
  54 Warning: my browser isn't able to compute factorials of numbers
  55 greater than 2 (it does't provide enough resources for the JavaScript
  56 interpreter; web pages are not supposed to be that computationally
  57 intensive).
  58
  59 3. (Easy) Write a function `listLenEq` that returns true just in case
  60 two lists have the
  61 same length.  That is,
  62
  63      listLenEq mylist (make_list junk (make_list junk (make_list junk empty)))
  64      ~~> true
  65
  66      listLenEq mylist (make_list junk (make_list junk empty))) ~~> false
  67
  68
  69 4. (Still easy) Now write the same function, but don't use the length
  70 function.
  71
  72 5. In assignment 2, we discovered that version 3-type lists (the ones
  73 that
  74 work like Church numerals) made it much easier to define operations
  75 like `map` and `filter`.  But now that we have recursion in our
  76 toolbox,
  77 reasonable map and filter functions for version 1 lists are within our
  78 reach.  Give definitions for `map` and a `filter` for verson 1 type
  79 lists.
  80
  81 #Computing with trees#
  82
  83 Linguists analyze natural language expressions into trees.
  84
  85 We'll need trees in future weeks, and tree structures provide good
  86 opportunities for learning how to write recursive functions.
  87 Making use of the resources we have at the moment, we can approximate
  88 trees as follows: instead of words, we'll use Church numerals.
  89 Then a tree will be a (version 1 type) list in which each element is
  90 itself a tree.  For simplicity, we'll adopt the convention that
  91 a tree of length 1 must contain a number as its only element.
  92
  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         let t1 = (make_list 1 empty) in
 121         let t2 = (make_list 2 empty) in
 122         let t3 = (make_list 3 empty) in
 123         let t12 = (make_list t1 (make_list t2 empty)) in
 124         let t23 = (make_list t2 (make_list t3 empty)) in
 125         let ta = (make_list t1 t23) in
 126         let tb = (make_list t12 t3) in
 127         let tc = (make_list t1 (make_list t23 empty)) in
 128
 129         sum-leaves t1 ~~> 1
 130         sum-leaves t2 ~~> 2
 131         sum-leaves t3 ~~> 3
 132         sum-leaves t12 ~~> 3
 133         sum-leaves t23 ~~> 5
 134         sum-leaves ta ~~> 6
 135         sum-leaves tb ~~> 6
 136         sum-leaves tc ~~> 6
 137
 138
 139 2.   Write a function that counts the number of leaves.
 140