Reversing a list

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 Assignment 4 hint 1 if you need some hints.)

Comparing lists for equality

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 Assignment 4 hint 2 if you need some hints.)

Enumerating the fringe of a leaf-labeled tree

First, read this: Implementing trees

Write an implementation of leaf-labeled trees. You can do something v3-like, or use the Y combinator, as you prefer.

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. And an operation extract_left that tells you what the left subtree is of a tree that isn't a leaf. (Presumably, extract_right will work similarly.)
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:
```
    .
   / \
  .   3
 / \
1   2
```
is [1;2;3]. And that is also the fringe of this tree:
```
    .
   / \
  1   .
     / \
    2   3
```
The two trees are different, but they have the same fringe. We're going to return later in the term to the problem of determining when two trees have the same fringe. For now, one straightforward way to determine this would be: enumerate the fringe of the first tree. That gives you a list. Enumerate the fringe of the second tree. That also gives you a list. Then compare the two lists to see if they're equal.

Write the fringe-enumeration function. It should work on the implementation of trees you designed in the previous step.

Then combine this with the list comparison function you wrote for question 2, to yield a same-fringe detector. (To use your list comparison function, you'll have to make sure you only use Church numerals as the labels of your leaves, though nothing enforces this self-discipline.)

Mutually-recursive functions

(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?
(More challenging.) Using our derivation of Y from the Week3 notes as a model, construct a pair Y1 and Y2 that behave in the way described.

(See Assignment 4 hint 3 if you need some hints.)