A tuple is a pair of functions. Using the lambda expressions below, a pair of a and b can be made using ‘pair a b’, and the first and second functions of p can be extracted using ‘first p’ and ‘second p’ respecively.
- pair = λabf.fab
- first = λp.p(λab.a)
- second = λp.p(λab.b)
A list is either empty, or consists of a head (a function) and a tail (another list). The most elegant way of representing a list is based on the representation of integer. The list containing a1, a2... ...an, is represented by λfx.fa1(fa2(...fan-1(fanx)...)). The lambda expression for the empty list, append function, head function and test for the empty list are:
- empty = λfx.x
- append = λalfx.fa(lfx)
- head = λl.l(λab.a)(any expression)
- isempty = λl.l(λab.false)true
‘append a l’ constructs a list with head a and tail l.
The tail function is much more complicated, and makes use of the tuples defined above. The principle is to start off with a pair (empty,empty), and at each stage turn the pair (x,y) into the pair (y,append a y), where a is the current list element, and then take the first element of the pair. The lambda expression is:
- tail=λl.first(l(λab.pair(second b)(append a (second b)))(pair empty empty))