Lambda calculus
Pairs

A pair (2-tuple) can be defined in terms of TRUE and FALSE, by using the Church encoding for pairs. For example, PAIR encapsulates the pair (x, y), FIRST returns the first element of the pair, and SECOND returns the second.

A linked list can be defined as either NIL for the empty list, or the PAIR of an element and a smaller list. The predicate NULL tests for the value NIL. (Alternatively, with NIL := FALSE, the construct l (λ h.λ t.λ z.deal_with_head_ h _and_tail_ t) (deal_with_nil) obviates the need for an explicit NULL test).

As an example of the use of pairs, the shift-and-increment function that maps (m, n) to (n, n + 1) can be defined as

which allows us to give perhaps the most transparent version of the predecessor function:
detectable_content:postscript