X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment4.mdwn;h=9b7ec2c028622dc92e17dced54403aa6043b8896;hp=54a3bf201d1914997fbf3d49cc669059d36a16e4;hb=HEAD;hpb=5a235579e3764fed888bdbd8465c373634c63984 diff --git a/assignment4.mdwn b/assignment4.mdwn deleted file mode 100644 index 54a3bf20..00000000 --- a/assignment4.mdwn +++ /dev/null @@ -1,89 +0,0 @@ -#Reversing a list# - -
    -
  1. How would you define an operation to reverse a list? (Don't peek at the -[[lambda_library]]! Try to figure it out on your own.) Choose whichever -implementation of list you like. Even then, there are various strategies you -can use. - -(See [[hints/Assignment 4 hint 1]] if you need some hints.) -
- - -#Comparing lists for equality# - - -
    -
  1. Suppose you have two lists of integers, `left` and `right`. You want to determine whether those lists are equal: that is, whether they have all the same members in the same order. (Equality for the lists we're working with is *extensional*, or parasitic on the equality of their members, and the list structure. Later in the course we'll see lists which aren't extensional in this way.) - -How would you implement such a list comparison? - -(See [[hints/Assignment 4 hint 2]] if you need some hints.) -
- - -#Enumerating the fringe of a leaf-labeled tree# - -First, read this: [[Implementing trees]] - -
    -
  1. blah - -(See [[hints/Assignment 4 hint 3]] if you need some hints.) -
- - -#Mutually-recursive functions# - -
    -
  1. (Challenging.) One way to define the function `even` is to have it hand off part of the work to another function `odd`: - - let even = \x. iszero x - ; if x == 0 then result is - true - ; else result turns on whether x's pred is odd - (odd (pred x)) - -At the same tme, though, it's natural to define `odd` in such a way that it hands off part of the work to `even`: - - let odd = \x. iszero x - ; if x == 0 then result is - false - ; else result turns on whether x's pred is even - (even (pred x)) - -Such a definition of `even` and `odd` is called **mutually recursive**. If you trace through the evaluation of some sample numerical arguments, you can see that eventually we'll always reach a base step. So the recursion should be perfectly well-grounded: - - even 3 - ~~> iszero 3 true (odd (pred 3)) - ~~> odd 2 - ~~> iszero 2 false (even (pred 2)) - ~~> even 1 - ~~> iszero 1 true (odd (pred 1)) - ~~> odd 0 - ~~> iszero 0 false (even (pred 0)) - ~~> false - -But we don't yet know how to implement this kind of recursion in the lambda calculus. - -The fixed point operators we've been working with so far worked like this: - - let X = Y T in - X <~~> T X - -Suppose we had a pair of fixed point operators, `Y1` and `Y2`, that operated on a *pair* of functions `T1` and `T2`, as follows: - - let X1 = Y1 T1 T2 in - let X2 = Y2 T1 T2 in - X1 <~~> T1 X1 X2 and - X2 <~~> T2 X1 X2 - -If we gave you such a `Y1` and `Y2`, how would you implement the above definitions of `even` and `odd`? - - -
  2. (More challenging.) Using our derivation of Y from the [Week3 notes](/week3/#index4h2) as a model, construct a pair `Y1` and `Y2` that behave in the way described. - -(See [[hints/Assignment 4 hint 4]] if you need some hints.) - -
-