Tuples and lists in lambda calculus


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.


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 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:

‘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:

Where now?

Found this useful? Share it:

Also in Lambda calculus: