Deadline: 5.30pm, Thursday 22 January 2004.
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.