## Tuples

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)

## Lists

A list is either empty, or consists of a head (any lambda expression) and a tail (another list).
The most elegant way of representing a list is based on the representation of integer.
The list containing a_{1}, a_{2}... ...a_{n}, is represented by λfx.fa_{1}(fa_{2}(...fa_{n-1}(fa_{n}x)...)).
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 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))