consconstructs (hence the name) memory objects which hold two values or pointers to values. These objects are referred to as (cons) cells, conses, 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 the
car(the first element), and a right half (the second element), referred to as the
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 and the : operator in Haskell, which adds an element to the beginning of a list.)
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)
caris the first element of the list and whose
cdris 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
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:
nil, the empty list
which is equivalent to the single expression:
or its shorthand:
The resulting value is the list:
(1 . (2 . (3 . nil)))
| | |
1 2 3
which is generally abbreviated as:
(1 2 3)
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)
cons. For example, the code:
results in the tree:
((1 . 2) . (3 . 4))
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:
| | |
1 2 3
to the following equivalent:
I sped up the code a bit by putting in side effects instead of having it cons like crazy.
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.
Con-Way Freight Honored by Local Decatur Army Reserve Veteran for Support, Presents Commemorative Flag Flown during Afghanistan Deployment
May 15, 2013; By a News Reporter-Staff News Editor at Defense & Aerospace Week -- U.S. Army Reserve Staff Sgt. Brian McCleskey, a driver sales...