assignment4.mdwn

   1 #Reversing a list#
   2
   3 <OL>
   4 <LI>How would you define an operation to reverse a list? (Don't peek at the
   5 [[lambda_library]]! Try to figure it out on your own.) Choose whichever
   6 implementation of list you like. Even then, there are various strategies you
   7 can use.
   8
   9 (See [[hints/Assignment 4 hint 1]] if you need some hints.)
  10 </OL>
  11
  12
  13 #Comparing lists for equality#
  14
  15
  16 <OL start=2>
  17 <LI>Suppose you have two lists of integers, `left` and `right`. You want to
  18 determine whether those lists are equal: that is, whether they have all the
  19 same members in the same order. (Equality for the lists we're working with is
  20 *extensional*, or parasitic on the equality of their members, and the list
  21 structure. Later in the course we'll see lists which aren't extensional in this
  22 way.)
  23
  24 How would you implement such a list comparison?
  25
  26 (See [[hints/Assignment 4 hint 2]] if you need some hints.)
  27 </OL>
  28
  29
  30 #Enumerating the fringe of a leaf-labeled tree#
  31
  32 First, read this: [[Implementing trees]]
  33
  34 <OL start=3>
  35 <LI>Write an implementation of leaf-labeled trees. You can do something v3-like, or use the Y combinator, as you prefer.
  36
  37         You'll need an operation `make_leaf` that turns a label into a new leaf. You'll need an operation `make_node` that takes two subtrees (perhaps leaves, perhaps other nodes) and joins them into a new tree. You'll need an operation `isleaf` that tells you whether a given tree is a leaf. And an operation `extract_label` that tells you what value is associated with a given leaf.
  38
  39 <LI>The **fringe** of a leaf-labeled tree is the list of values at its leaves, ordered from left to right. For example, the fringe of this tree:
  40
  41                 .
  42            / \
  43           .   3
  44          / \
  45         1   2
  46
  47 is [1;2;3]. And that is also the fringe of this tree:
  48
  49                 .
  50            / \
  51           1   .
  52              / \
  53         2   3
  54
  55 The two trees are different, but they have the same fringe. We're going to
  56 return later in the term to the problem of determining when two trees have the
  57 same fringe. For now, one straightforward way to determine this would be:
  58 enumerate the fringe of the first tree. That gives you a list. Enumerate the
  59 fringe of the second tree. That also gives you a list. Then compare the two
  60 lists to see if they're equal. (You just programmed this above.)
  61
  62 Write the fringe-enumeration function. It should work on the implementation of
  63 trees you designed in the previous step.
  64
  65 (See [[hints/Assignment 4 hint 3]] if you need some hints.)
  66 </OL>
  67
  68
  69
  70 #Mutually-recursive functions#
  71
  72 <OL start=4>
  73 <LI>(Challenging.) One way to define the function `even` is to have it hand off
  74 part of the work to another function `odd`:
  75
  76         let even = \x. iszero x
  77                                         ; if x == 0 then result is
  78                                         true
  79                                         ; else result turns on whether x's pred is odd
  80                                         (odd (pred x))
  81
  82 At the same tme, though, it's natural to define `odd` in such a way that it
  83 hands off part of the work to `even`:
  84
  85         let odd = \x. iszero x
  86                                         ; if x == 0 then result is
  87                                         false
  88                                         ; else result turns on whether x's pred is even
  89                                         (even (pred x))
  90
  91 Such a definition of `even` and `odd` is called **mutually recursive**. If you
  92 trace through the evaluation of some sample numerical arguments, you can see
  93 that eventually we'll always reach a base step. So the recursion should be
  94 perfectly well-grounded:
  95
  96         even 3
  97         ~~> iszero 3 true (odd (pred 3))
  98         ~~> odd 2
  99         ~~> iszero 2 false (even (pred 2))
 100         ~~> even 1
 101         ~~> iszero 1 true (odd (pred 1))
 102         ~~> odd 0
 103         ~~> iszero 0 false (even (pred 0))
 104         ~~> false
 105
 106 But we don't yet know how to implement this kind of recursion in the lambda
 107 calculus.
 108
 109 The fixed point operators we've been working with so far worked like this:
 110
 111         let X = Y T in
 112         X <~~> T X
 113
 114 Suppose we had a pair of fixed point operators, `Y1` and `Y2`, that operated on
 115 a *pair* of functions `T1` and `T2`, as follows:
 116
 117         let X1 = Y1 T1 T2 in
 118         let X2 = Y2 T1 T2 in
 119         X1 <~~> T1 X1 X2 and
 120         X2 <~~> T2 X1 X2
 121
 122 If we gave you such a `Y1` and `Y2`, how would you implement the above
 123 definitions of `even` and `odd`?
 124
 125
 126 <LI>(More challenging.) Using our derivation of Y from the [Week3
 127 notes](/week3/#index4h2) as a model, construct a pair `Y1` and `Y2` that behave
 128 in the way described.
 129
 130 (See [[hints/Assignment 4 hint 4]] if you need some hints.)
 131
 132 </OL>
 133