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))
This article was last edited on 17th October 2014. The author can be contacted using the form below.
Back to home page
Bookmark with: