Editing Cons (section)

==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