Cons

From Free net encyclopedia

In computer programming, cons is a fundamental function in all dialects of the Lisp programming language. cons constructs (hence the name) memory objects holding two values/pointers. These objects are referred to as (cons) cells, conses, or (in Scheme) pairs. In Lisp jargon, the expression "to cons x onto y" means to construct a new object with (cons x y).

The name cons and the expression "to cons onto" are also found in more general functional programming jargon. Sometimes operators that have the same purpose (such as :: in Standard ML) are pronounced "cons".

Contents 1 Use 1.1 Lists 1.2 Trees 2 Use in Conversation 3 Similar procedures on lists

Use

Although cons cells can be used to implement ordered pairs of simplex data, they are probably more commonly used to construct more complex compound data structures, notably lists and binary trees.

For example, the Lisp expression (cons 1 2) constructs a cell holding 1 in its left half (the so-called car field) and 2 in its right half (the cdr field). In Lisp notation:

(1 . 2)

Lists

A list holding the elements 1, 2, 3 in that order can be created by the following steps:

1. Cons 3 onto the special object nil (which denotes the "empty list", the list of zero elements)
2. Cons 2 onto the result
3. Cons 1 onto the result

In one expression:

(cons 1 (cons 2 (cons 3 nil)))

The resulting value is the list

(1 . (2 . (3 . nil)))

i.e.

  *
 / \
1   *
   / \
  2   *
     / \
    3   nil

which may be abbreviated to

(1 2 3)

Trees

Binary trees, storing data in their leaves, may be constructed similarly:

(cons (cons 1 2) (cons 3 4))

results in the tree

((1 . 2) . (3 . 4))

i.e.

   *
  / \
 *   *
/ \ / \
1 2 3 4

Use in Conversation

cons is sometimes used colloquially in conversation (notably at MIT), usually in the expression "cons up". For example:

Can you cons up that email I sent to ec-discuss two weeks ago?

The item being "cons'd up" is the first argument to the operator, with the implied second argument being the list of all current information to hand. See also car and cdr.

Similar procedures on lists

cons can be used to add one element to the front of an existing linked list. To create a list from one or more elements directly, the list procedure is used. To concatenate two existing linked lists, the append procedure is used.