assignment3.mdwn

   1 Assignment 3
   2 ------------
   3
   4 Erratum corrected 11PM Sun 3 Oct: the following line
   5
   6         let tb = (make_list t12 (make_list t3 empty)) in
   7
   8 originally read
   9
  10         let tb = (make_list t12 t3) in
  11
  12 This has been corrected below, and in the preloaded evaluator for
  13 working on assignment 3, available here: [[assignment 3 evaluator]].
  14
  15 <hr>
  16
  17 Once again, the lambda evaluator will make working through this
  18 assignment much faster and more secure.
  19
  20 #Writing recursive functions on version 1 style lists#
  21
  22 Recall that version 1 style lists are constructed like this (see
  23 [[lists and numbers]]):
  24
  25         ; booleans
  26         let true = \x y. x in
  27         let false = \x y. y in
  28         let and = \l r. l (r true false) false in
  29
  30         let make_pair = \f s g. g f s in
  31         let get_fst = true 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
  38
  39         ; a list of numbers to experiment on
  40         let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
  41
  42         ; church numerals
  43         let iszero = \n. n (\x. false) true in
  44         let succ = \n s z. s (n s z) in
  45         let add = \l r. l succ r in
  46         let mul = \m n s. m (n s) in
  47         let pred = (\shift n. n shift (make\_pair 0 0) get\_snd) (\p. p (\x y. make\_pair (succ x) x)) in
  48         let leq = \m n. iszero(n pred m) in
  49         let eq = \m n. and (leq m n)(leq n m) in
  50
  51         ; a fixed-point combinator for defining recursive functions
  52         let Y = \f. (\h. f (h h)) (\h. f (h h)) in
  53         let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
  54         let fold = Y (\f l g z. isempty l z (g (head l)(f (tail l) g z))) in
  55
  56         eq 2 2 yes no
  57
  58
  59 Then `length mylist` evaluates to 3.
  60
  61 1. What does `head (tail (tail mylist))` evaluate to?
  62
  63 2. Using the `length` function as a model, and using the predecessor
  64 function, write a function that computes factorials.  (Recall that n!,
  65 the factorial of n, is n times the factorial of n-1.)
  66
  67         Warning: it takes a long time for my browser to compute factorials larger than 4!
  68
  69 3. (Easy) Write a function `equal_length` that returns true just in case
  70 two lists have the same length.  That is,
  71
  72                 equal_length mylist (make_list junk (make_list junk (make_list junk empty))) ~~> true
  73
  74                 equal_length mylist (make_list junk (make_list junk empty))) ~~> false
  75
  76
  77 4. (Still easy) Now write the same function, but don't use the length
  78 function.
  79
  80 5. In assignment 2, we discovered that version 3-type lists (the ones
  81 that
  82 work like Church numerals) made it much easier to define operations
  83 like `map` and `filter`.  But now that we have recursion in our
  84 toolbox,
  85 reasonable map and filter functions for version 1 lists are within our
  86 reach.  Give definitions for `map` and a `filter` for verson 1 type
  87 lists.
  88
  89 #Computing with trees#
  90
  91 Linguists analyze natural language expressions into trees.
  92
  93 We'll need trees in future weeks, and tree structures provide good
  94 opportunities for learning how to write recursive functions.
  95 Making use of the resources we have at the moment, we can approximate
  96 trees as follows: instead of words, we'll use Church numerals.
  97 Then a tree will be a (version 1 type) list in which each element is
  98 itself a tree.  For simplicity, we'll adopt the convention that
  99 a tree of length 1 must contain a number as its only element.
 100
 101 Then we have the following representations:
 102
 103 <pre>
 104    (a)           (b)             (c)
 105     .
 106    /|\            /\              /\
 107   / | \          /\ 3            1 /\
 108   1 2  3        1  2               2 3
 109
 110 [[1];[2];[3]]  [[[1];[2]];[3]]   [[1];[[2];[3]]]
 111 </pre>
 112
 113 Limitations of this scheme include the following: there is no easy way
 114 to label a constituent with a syntactic category (S or NP or VP,
 115 etc.), and there is no way to represent a tree in which a mother has a
 116 single daughter.
 117
 118 When processing a tree, you can test for whether the tree contains
 119 only a numeral (in which case the tree is leaf node) by testing for
 120 whether the length of the list is less than or equal to 1.  This will
 121 be your base case for your recursive functions that operate on these
 122 trees.
 123
 124 <OL start=6>
 125 <LI>Write a function that sums the values at the leaves in a tree.
 126
 127 Expected behavior:
 128
 129         let t1 = (make_list 1 empty) in
 130         let t2 = (make_list 2 empty) in
 131         let t3 = (make_list 3 empty) in
 132         let t12 = (make_list t1 (make_list t2 empty)) in
 133         let t23 = (make_list t2 (make_list t3 empty)) in
 134         let ta = (make_list t1 t23) in
 135         let tb = (make_list t12 (make_list t3 empty)) in
 136         let tc = (make_list t1 (make_list t23 empty)) in
 137
 138         sum-leaves t1 ~~> 1
 139         sum-leaves t2 ~~> 2
 140         sum-leaves t3 ~~> 3
 141         sum-leaves t12 ~~> 3
 142         sum-leaves t23 ~~> 5
 143         sum-leaves ta ~~> 6
 144         sum-leaves tb ~~> 6
 145         sum-leaves tc ~~> 6
 146
 147
 148 <LI>Write a function that counts the number of leaves.
 149
 150 </OL>
 151