Cons

It is loosely related to the object-oriented notion of a constructor, which creates a new object given arguments, and more closely related to the constructor function of an algebraic data type system.

The word "cons" and expressions like "to cons onto" are also part of a more general functional programming jargon. Sometimes operators that have a similar purpose, especially in the context of list processing, are pronounced "cons". (A good example is the :: operator in ML, Scala, F#, Lean, Rocq, and Elm or the : operator in Haskell, which adds an element to the beginning of a list.)

Use

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

Ordered pairs

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, the value (cons 1 2) looks like:

(1 . 2)

Note the dot between 1 and 2; this indicates that the S-expression is a "dotted pair" (a so-called "cons pair"), rather than a "list."

Lists

In Lisp, lists are implemented on top of cons pairs. More specifically, any list structure in Lisp is either:

1. An empty list (), which is a special object usually called nil.
2. A cons cell whose car is the first element of the list and whose cdr is a list containing the rest of the elements.

This forms the basis of a simple, singly linked list structure whose contents can be manipulated with cons, car, and cdr. Note that nil is the only list that is not also a cons pair. As an example, consider a list whose elements are 1, 2, and 3. Such a list can be created in three steps:

1. Cons 3 onto nil, the empty list
2. Cons 2 onto the result
3. Cons 1 onto the result

which is equivalent to the single expression:

<span id="mwrw"></span><span class="p" id="mwsA">(</span><span class="nb" id="mwsQ">cons</span><span class="w" id="mwsg"> </span><span class="mi" id="mwsw">1</span><span class="w" id="mwtA"> </span><span class="p" id="mwtQ">(</span><span class="nb" id="mwtg">cons</span><span class="w" id="mwtw"> </span><span class="mi" id="mwuA">2</span><span class="w" id="mwuQ"> </span><span class="p" id="mwug">(</span><span class="nb" id="mwuw">cons</span><span class="w" id="mwvA"> </span><span class="mi" id="mwvQ">3</span><span class="w" id="mwvg"> </span><span class="no" id="mwvw">nil</span><span class="p" id="mwwA">)))</span>

or its shorthand:

<span id="mwxA"></span><span class="p" id="mwxQ">(</span><span class="nb" id="mwxg">list</span><span class="w" id="mwxw"> </span><span class="mi" id="mwyA">1</span><span class="w" id="mwyQ"> </span><span class="mi" id="mwyg">2</span><span class="w" id="mwyw"> </span><span class="mi" id="mwzA">3</span><span class="p" id="mwzQ">)</span>

The resulting value is the list:

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

i.e.

*--*--*--nil | | | 1 2 3

which is generally abbreviated as:

(1 2 3)

Thus, cons can be used to add one element to the front of an existing linked list. For example, if x is the list we defined above, then (cons 5 x) will produce the list:

(5 1 2 3)

Another useful list procedure is append, which concatenates two existing lists (i.e. combines two lists into a single list).

Trees

Binary trees that only store data in their leaves are also easily constructed with cons. For example, the code:

<span id="mw7w"></span><span class="p" id="mw8A">(</span><span class="nb" id="mw8Q">cons</span><span class="w" id="mw8g"> </span><span class="p" id="mw8w">(</span><span class="nb" id="mw9A">cons</span><span class="w" id="mw9Q"> </span><span class="mi" id="mw9g">1</span><span class="w" id="mw9w"> </span><span class="mi" id="mw-A">2</span><span class="p" id="mw-Q">)</span><span class="w" id="mw-g"> </span><span class="p" id="mw-w">(</span><span class="nb" id="mw_A">cons</span><span class="w" id="mw_Q"> </span><span class="mi" id="mw_g">3</span><span class="w" id="mw_w"> </span><span class="mi" id="mwAQA">4</span><span class="p" id="mwAQE">))</span>

results in the tree:

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

i.e.

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

Technically, the list (1 2 3) in the previous example is also a binary tree, one which happens to be particularly unbalanced. To see this, simply rearrange the diagram:

*--*--*--nil | | | 1 2 3

to the following equivalent:

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