# Tuples And Lists In Lambda Calculus

## 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.pab.a)
• second = λp.pab.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 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.lab.a)(any expression)
• isempty = λl.lab.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(lab.pair(second b)(append a (second b)))(pair empty empty))