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>blah
  36
  37 (See [[hints/Assignment 4 hint 3]] if you need some hints.)
  38 </OL>
  39
  40
  41 #Mutually-recursive functions#
  42
  43 <OL start=4>
  44 <LI>(Challenging.) One way to define the function `even` is to have it hand off
  45 part of the work to another function `odd`:
  46
  47         let even = \x. iszero x
  48                                         ; if x == 0 then result is
  49                                         true
  50                                         ; else result turns on whether x's pred is odd
  51                                         (odd (pred x))
  52
  53 At the same tme, though, it's natural to define `odd` in such a way that it
  54 hands off part of the work to `even`:
  55
  56         let odd = \x. iszero x
  57                                         ; if x == 0 then result is
  58                                         false
  59                                         ; else result turns on whether x's pred is even
  60                                         (even (pred x))
  61
  62 Such a definition of `even` and `odd` is called **mutually recursive**. If you
  63 trace through the evaluation of some sample numerical arguments, you can see
  64 that eventually we'll always reach a base step. So the recursion should be
  65 perfectly well-grounded:
  66
  67         even 3
  68         ~~> iszero 3 true (odd (pred 3))
  69         ~~> odd 2
  70         ~~> iszero 2 false (even (pred 2))
  71         ~~> even 1
  72         ~~> iszero 1 true (odd (pred 1))
  73         ~~> odd 0
  74         ~~> iszero 0 false (even (pred 0))
  75         ~~> false
  76
  77 But we don't yet know how to implement this kind of recursion in the lambda
  78 calculus.
  79
  80 The fixed point operators we've been working with so far worked like this:
  81
  82         let X = Y T in
  83         X <~~> T X
  84
  85 Suppose we had a pair of fixed point operators, `Y1` and `Y2`, that operated on
  86 a *pair* of functions `T1` and `T2`, as follows:
  87
  88         let X1 = Y1 T1 T2 in
  89         let X2 = Y2 T1 T2 in
  90         X1 <~~> T1 X1 X2 and
  91         X2 <~~> T2 X1 X2
  92
  93 If we gave you such a `Y1` and `Y2`, how would you implement the above
  94 definitions of `even` and `odd`?
  95
  96
  97 <LI>(More challenging.) Using our derivation of Y from the [Week3
  98 notes](/week3/#index4h2) as a model, construct a pair `Y1` and `Y2` that behave
  99 in the way described.
 100
 101 (See [[hints/Assignment 4 hint 4]] if you need some hints.)
 102
 103 </OL>
 104