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