cons

<h2 id="use">Use</h2>
<p>Although cons cells can be used to hold <a href="/facts/Ordered_pair/EInLVI0r">ordered pairs</a> of data, they are more commonly used to construct more complex compound data structures, notably <a href="/facts/Linked_list/Ik4JTgJW">lists</a> and <a href="/facts/Binary_tree/TDV7GMpu">binary trees</a>.
</p>
<h3>Ordered pairs</h3>
<p>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:
</p>
(1 . 2)

<p>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."
</p>
<h3>Lists</h3>

<p>In Lisp, lists are implemented on top of cons pairs. More specifically, any list structure in Lisp is either:
</p>
<ol><li>An empty list (), which is a special object usually called nil.</li>
<li>A cons cell whose car is the first element of the list and whose cdr is a <a href="/facts/List/tpX6LYVY">list</a> containing the rest of the elements.</li></ol>
<p>This forms the basis of a simple, <a href="/facts/Linked_list/Ik4JTgJW">singly linked list</a> 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:
</p>
<ol><li>Cons 3 onto nil, the empty list</li>
<li>Cons 2 onto the result</li>
<li>Cons 1 onto the result</li></ol>
<p>which is equivalent to the single expression:
</p>
 (cons 1 (cons 2 (cons 3 nil)))

<p>or its shorthand:
</p>
 (list 1 2 3)

<p>The resulting value is the list:
</p>
(1 . (2 . (3 . nil)))

<p>i.e.
</p>
 *--*--*--nil
 |  |  |
 1  2  3

<p>which is generally abbreviated as:
</p>
(1 2 3)

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

<p>Another useful list procedure is <a href="/facts/Append/eLQNt2yU">append</a>, which <a href="/facts/Concatenation/1npYg6rc">concatenates</a> two existing lists (i.e. combines two lists into a single list).
</p>
<h3>Trees</h3>
<p><a href="/facts/Binary_tree/TDV7GMpu">Binary trees</a> that only store data in their <a href="/facts/Leaf_node/RcXz9noF">leaves</a> are also easily constructed with cons. For example, the code:
</p>
 (cons (cons 1 2) (cons 3 4))

<p>results in the tree:
</p>
((1 . 2) . (3 . 4))

<p>i.e.
</p>
   *
  / \
 *   *
/ \ / \
1 2 3 4

<p>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:
</p>
 *--*--*--nil
 |  |  |
 1  2  3

<p>to the following equivalent:
</p>
   *
  / \
 1   *
    / \
   2   *
      / \
     3  nil

<h2 id="use-in-conversation">Use in conversation</h2>
<p>Cons can refer to the general process of <a href="/facts/Dynamic_memory_allocation/vthLkUpz">memory allocation</a>, as opposed to using destructive operations of the kind that would be used in an imperative programming language. For example:
</p>
<blockquote><p>I sped up the code a bit by putting in <a href="/facts/Side_effect_(computer_science)/AU3GlLzG">side effects</a> instead of having it cons ridiculously.</p></blockquote>
<h2 id="functional-implementation">Functional implementation</h2>
<p>Since Lisp has <a href="/facts/First-class_function/dtMzp81k">first-class functions</a>, all data structures, including cons cells, can be implemented using functions. For example, in <a href="/facts/Scheme_(programming_language)/0aGdf3SC">Scheme</a>:
</p>
(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)))

<p>This technique is known as <a href="/facts/Church_encoding/IlLPzswH">Church encoding</a>. It re-implements the <i>cons</i>, <i>car</i>, and <i>cdr</i> operations, using a function as the "cons cell". Church encoding is a usual way of defining data structures in pure <a href="/facts/Lambda_calculus/DaD3RuQ4">lambda calculus</a>, an abstract, theoretical model of computation that is closely related to Scheme.
</p><p>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.
</p><p>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.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as <a href="/facts/Java_(programming_language)/9ScgFyAL">Java</a>, using interfaces instead of lambdas.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Lisp_(programming_language)/xJHA3CrX">Lisp (programming language)</a></li>
<li><a href="/facts/CAR_and_CDR/cC7hhymV">CAR and CDR</a></li>
<li><a href="/facts/Constructor_(computer_science)/8JNHsH5H">Constructor (computer science)</a></li>
<li><a href="/facts/Algebraic_data_type/Fn9KhnAb">Algebraic data type</a></li>
<li><a href="/facts/Hash_consing/k7B1oy80">Hash consing</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.cs.cmu.edu/~dst/Lisp/sdraw/">SDRAW</a>, <a href="/facts/Common_Lisp/mq1pRbSF">Common Lisp</a>  code for drawing draws cons cell structures. From David S. Touretzky.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>"Efficient Interpretation by Transforming Data Types and Patterns to Functions" (PDF). Archived from the original (PDF) on 2010-03-31. Retrieved 2009-03-01. <a href="https://web.archive.org/web/20100331083602/http://www.st.cs.ru.nl/papers/2006/janj2006-TFP06-EfficientInterpretation.pdf" target="_blank">https://web.archive.org/web/20100331083602/http://www.st.cs.ru.nl/papers/2006/janj2006-TFP06-EfficientInterpretation.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

cons open-in-new

cons