SE547: Homework 2

Deadline: 5.30pm, Thursday 22 January 2004.

Homework

Consider the following coding of linked lists in the lambda-calculus:

Nil = f . g . f
Cons h . t . f . g . g h t
Hd = l . l False ( x . y . x )
Tl = l . l False ( x . y . y )
IsNil = l . l True ( x . y . False )

1. Show the following:

Hd (Cons M N) = M
Tl (Cons M N) = N
IsNil Nil = True
IsNil (Cons M N) = False

2. Using these functions, and others discussed in class, write a function Last (which returns the last element in a list) and show the following properties are true of it:

Last Nil = Nil
Last (Cons M Nil) = M
Last (Cons L (Cons M N)) = Last (Cons M N)

Hint: use recursion!

Submit your answer (either as a plain text file, a PDF file, an HTML file, or scanned handwriting) using Courses On Line.