## 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 = λ
`a``b``f`.`f``a``b` - first = λ
`p`.`p`(λ`a``b`.`a`) - second = λ
`p`.`p`(λ`a``b`.`b`)

## Lists

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 `a _{1}`,

`a`... ...

_{2}`a`, is represented by λ

_{n}`f`

`x`.

`f`

`a`(

_{1}`f`

`a`(...

_{2}`f`

`a`(

_{n-1}`f`

`a`

_{n}`x`)...)). The lambda expression for the empty list, append function, head function and test for the empty list are:

- empty = λ
`f``x`.`x` - append = λ
`a``l``f``x`.`f``a`(`l``f``x`) - head = λ
`l`.`l`(λ`a``b`.`a`)(any expression) - isempty = λ
`l`.`l`(λ`a``b`.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`(λ`a``b`.pair(second`b`)(append`a`(second`b`)))(pair empty empty))