> I'm not sure which of the two solutions presented here is better. The one given in the hint traverses the list only once; whereas the one gotten by reversing the list and getting the last member of the result traverses the list twice. But the former strategy does more complicated stuff at each step of the traversal (both conceptually and more applications), so in the end it might be computationally "cheaper" to use the latter strategy.
+ > Here is yet a third solution, which is probably the most efficient:
+ > let box = \a. \v. v a in
+ > let left_head = \xs. xs (\b x. (K (b (K x)))) (box err) I in
+ > ...
8. 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. How would you implement such a list comparison? You can write it in Scheme or Kapulet using `letrec`, or if you want more of a challenge, in the Lambda Calculus using your preferred encoding for lists. If you write it in Scheme, don't rely on applying the built-in comparison operator `equal?` to the lists themselves. (Nor on the operator `eqv?`, which might not do what you expect.) You can however rely on the comparison operator `=` which accepts only number arguments. If you write it in the Lambda Calculus, you can use your implementation of `leq?`, requested below, to write an equality operator for Church-encoded numbers. [[Here is a hint|assignment3 hint3]], if you need it.
> let pred = \n. n shift (pair 0 err) snd in
> ...
- > Here is another solution, due to Martin Bunder and F. Urbanek:
+ > Here is another solution, that is attributed variously to Martin Bunder and F. Urbanek, or J. Velmans:
> let box = \a. \v. v a in
> let pred = \n. \s z. n (\b. box (b s)) (K z) I in