View source for Cons

{{short description|Function and primitive data structure in Lisp and other functional programming languages}}
{{about|the Lisp programming function}}
{{more citations needed|date=January 2019}}
{{lowercase title}}
In [[computer programming]], '''{{lisp2|cons}}''' ({{IPAc-en|ˈ|k|ɒ|n|z}} or {{IPAc-en|ˈ|k|ɒ|n|s}}) is a fundamental [[subroutine|function]] in most dialects of the [[Lisp (programming language)|Lisp]] programming language. {{lisp2|cons}} '''''cons'''tructs'' memory objects which hold two values or pointers to two values. These objects are referred to as (cons) cells, conses, non-atomic [[s-expressions]] ("NATSes"), or (cons) [[ordered pair|pairs]]. In Lisp jargon, the expression "to cons ''x'' onto ''y''" means to construct a new object with <code>(cons ''x'' ''y'')</code>. The resulting pair has a left half, referred to as the {{lisp2|car}} (the first element, or ''[[CAR and CDR|'''c'''ontents of the '''a'''ddress part of '''r'''egister]]''), and a right half, referred to as the {{lisp2|cdr}} (the second element, or ''[[CAR and CDR|'''c'''ontents of the '''d'''ecrement part of '''r'''egister]]'').

It is loosely related to the [[object-oriented programming|object-oriented]] notion of a [[constructor (computer science)|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 [[Operator (programming)|operators]] that have a similar purpose, especially in the context of list processing, are pronounced "cons". (A good example is the <code>::</code> operator in [[ML programming language|ML]], [[Scala (programming language)|Scala]], [[F Sharp (programming language)|F#]], [[Lean (proof assistant)|Lean]], [[Coq (software)|Coq]], and [[Elm (programming language)|Elm]] or the <code>:</code> operator in [[Haskell (programming language)|Haskell]], which adds an element to the beginning of a list.)

==Use==
Although cons cells can be used to hold [[ordered pair]]s of data, they are more commonly used to construct more complex compound data structures, notably [[Linked list|lists]] and [[binary tree]]s.

===Ordered pairs===
For example, the Lisp expression {{lisp2|(cons 1 2)}} constructs a cell holding 1 in its left half (the so-called {{lisp2|car}} field) and 2 in its right half (the {{lisp2|cdr}} field). In Lisp notation, the value {{lisp2|(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===
[[Image:Cons-cells.svg|thumb|left|350px|Cons cell diagram for the list (42 69 613), written with <code>cons</code>: <syntaxhighlight lang="lisp">(cons 42 (cons 69 (cons 613 nil)))</syntaxhighlight> and written with <code>list</code>: <syntaxhighlight lang="lisp">(list 42 69 613)</syntaxhighlight>]]
{{clear}}
In Lisp, lists are implemented on top of cons pairs. More specifically, any list structure in Lisp is either:

#An empty list {{lisp2|()}}, which is a special object usually called {{lisp2|nil}}.
#A cons cell whose {{lisp2|car}} is the first element of the list and whose {{lisp2|cdr}} is a [[list]] containing the rest of the elements.
This forms the basis of a simple, [[Linked list|singly linked list]] structure whose contents can be manipulated with {{lisp2|cons}}, {{lisp2|car}}, and {{lisp2|cdr}}. Note that {{lisp2|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:

#Cons 3 onto {{lisp2|nil}}, the empty list
#Cons 2 onto the result
#Cons 1 onto the result

which is equivalent to the single expression:

 <syntaxhighlight lang="lisp">(cons 1 (cons 2 (cons 3 nil)))</syntaxhighlight>

or its shorthand:

 <syntaxhighlight lang="lisp">(list 1 2 3)</syntaxhighlight>

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, {{lisp2|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 {{lisp2|(cons 5 x)}} will produce the list:

 (5 1 2 3)

Another useful list procedure is [[Append#Lisp|append]], which [[Concatenation|concatenates]] two existing lists (i.e. combines two lists into a single list).

===Trees===
[[Binary tree]]s that only store data in their [[Leaf node|leaves]] are also easily constructed with {{lisp2|cons}}. For example, the code:

 <syntaxhighlight lang="lisp">(cons (cons 1 2) (cons 3 4))</syntaxhighlight>

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 [[Dynamic memory allocation|memory allocation]], as opposed to using destructive operations of the kind that would be used in an imperative programming language.{{citation needed|date=October 2022}} For example:

<blockquote>I sped up the code a bit by putting in [[side effect (computer science)|side effect]]s instead of having it cons ridiculously.</blockquote>

==Functional implementation==
Since Lisp has [[first-class function]]s, all data structures, including cons cells, can be implemented using functions. For example, in [[Scheme (programming language)|Scheme]]:
<syntaxhighlight lang="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)))
</syntaxhighlight>
This technique is known as [[Church encoding#Church pairs|Church encoding]]. It re-implements the ''cons'', ''car'', and ''cdr'' operations, using a function as the "cons cell". Church encoding is a 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 introduces 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.<ref>{{cite web |url=http://www.st.cs.ru.nl/papers/2006/janj2006-TFP06-EfficientInterpretation.pdf |title=Efficient Interpretation by Transforming Data Types and Patterns to Functions |accessdate=2009-03-01 |url-status=dead |archiveurl=https://web.archive.org/web/20100331083602/http://www.st.cs.ru.nl/papers/2006/janj2006-TFP06-EfficientInterpretation.pdf |archivedate=2010-03-31 }}</ref>
This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as [[Java (programming language)|Java]], using interfaces instead of lambdas.

==See also==
* [[Lisp (programming language)]]
* [[CAR and CDR]]
* [[Constructor (computer science)]]
* [[Algebraic data type]]
* [[Hash consing]]

==References==
<references/>

==External links==
* [https://www.cs.cmu.edu/~dst/Lisp/sdraw/ SDRAW], [[Common Lisp]]  code for drawing draws cons cell structures. From David S. Touretzky.

{{Data types}}

[[Category:Functional programming]]
[[Category:Lisp (programming language)]]
[[Category:Articles with example Lisp (programming language) code]]
[[Category:Articles with example Scheme (programming language) code]]
[[Category:Composite data types]]
[[Category:Data types]]