 cons

This article is about the Lisp programming function. For other uses, see Cons (disambiguation).
In computer programming, cons ( /ˈkɒnz/ or /ˈkɒns/) is a fundamental function in most dialects of the Lisp programming language.
cons
constructs memory objects which hold two values or pointers to values. These objects are referred to as (cons) cells, conses, nonatomic sexpressions ("NATSes"), or (cons) pairs. In Lisp jargon, the expression "to cons x onto y" means to construct a new object with(cons x y)
. The resulting pair has a left half, referred to as thecar
(the first element), and a right half (the second element), referred to as thecdr
.It is loosely related to the objectoriented 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 and Scala, which adds an element to the beginning of a list.)
Contents
Use
Although cons cells can be used to hold ordered pairs of simplex data, they are 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 socalledcar
field) and 2 in its right half (thecdr
field). In Lisp notation, the value(cons 1 2)
looks like:(1 . 2)
Note the dot between 1 and 2; this indicates that the Sexpression is a "dotted 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:
 An empty list
()
, which is a special object usually callednil
.  A cons cell whose
car
is the first element of the list and whosecdr
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
, andcdr
. Note thatnil
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: Cons 3 onto
nil
, the empty list  Cons 2 onto the result
 Cons 1 onto the result
which is equivalent to the single expression:
(cons 1 (cons 2 (cons 3 nil)))
or its shorthand:
(list 1 2 3)
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:(cons (cons 1 2) (cons 3 4))
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
Use in conversation
Cons can refer to the general process of memory allocation, as opposed to using destructive operations of the kind that would be used in an imperative programming language. For example:
I sped up the code a bit by putting in side effects instead of having it cons like crazy.
Not technically fundamental
Since Lisp has firstclass functions, all data structures, including cons cells, are not fundamentally necessary to the language, since all data structures can be implemented using functions. For example, in Scheme:
(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p))) (define (cdr z) (z (lambda (p q) q)))
The above code reimplements the cons, car, and cdr operations, using a function as the "cons cell". This is the usual way of defining data structures in pure lambda calculus, an abstract, theoretical model of computation that is closely related to Scheme.
This implementation, while academically interesting, is impractical because it renders cons cells indistinguishable from any other Scheme procedure, as well as introducing unnecessary computational inefficiencies.
However, the same kind of encoding can be used for more complex algebraic data types with variants, where it may even turn out to be more efficient than other kinds of encoding.^{[1]} This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as Java, using interfaces instead of lambdas.
See also
 Lisp (programming language)
 CAR and CDR
 Constructor (computer science)
 Algebraic data type
 Hash consing
References
External links
 SDRAW, Common Lisp code for drawing draws cons cell structures. From David S. Touretzky.
Data types Uninterpreted Numeric  Integer
 Fixedpoint
 Floatingpoint
 Rational
 Complex
 Bignum
 Interval
 Decimal
Text Pointer Composite Other  Boolean
 Bottom type
 Collection
 Enumerated type
 Exception
 Function type
 Opaque data type
 Recursive data type
 Semaphore
 Stream
 Top type
 Type class
 Unit type
 Void
Related topics  Abstract data type
 Data structure
 Interface
 Kind
 Primitive data type
 Subtyping
 Template
 Type constructor
 Parametric polymorphism
Categories: Functional programming
 Lisp programming language
 Articles with example Lisp code
 Articles with example Scheme code
 Composite data types
 Data types
 An empty list
Wikimedia Foundation. 2010.