<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 0.6.5 (Tue Nov 15 1994) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>2.4. Lists and Conses</TITLE>
</HEAD>
<BODY>
<meta name="description" value=" Lists and Conses">
<meta name="keywords" value="clm">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
<b>Common Lisp the Language, 2nd Edition</b>
 <BR> <HR><A NAME=tex2html1854 HREF="node29.html"><IMG ALIGN=BOTTOM ALT="next" SRC="icons/next_motif.gif"></A> <A NAME=tex2html1852 HREF="node15.html"><IMG ALIGN=BOTTOM ALT="up" SRC="icons/up_motif.gif"></A> <A NAME=tex2html1846 HREF="node27.html"><IMG ALIGN=BOTTOM ALT="previous" SRC="icons/previous_motif.gif"></A> <A NAME=tex2html1856 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="contents" SRC="icons/contents_motif.gif"></A> <A NAME=tex2html1857 HREF="index.html"><IMG ALIGN=BOTTOM ALT="index" SRC="icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME=tex2html1855 HREF="node29.html"> Arrays</A>
<B>Up:</B> <A NAME=tex2html1853 HREF="node15.html"> Data Types</A>
<B> Previous:</B> <A NAME=tex2html1847 HREF="node27.html"> Symbols</A>
<HR> <P>
<H1><A NAME=SECTION00640000000000000000>2.4. Lists and Conses</A></H1>
<P>
<A NAME=1158>A</A>
<tt>cons</tt> is a record structure containing two components
called the <i>car</i> and the <i>cdr</i>.  Conses are used primarily
to represent lists.
<P>
A <i>list</i> is recursively defined to be either the empty list
or a cons whose <i>cdr</i> component is a list.
A list is therefore a chain of conses linked by their <i>cdr</i> components
and terminated by <tt>nil</tt>, the empty list.  The <i>car</i> components of the conses
are called the <i>elements</i> of the list.  For each element of the list
there is a cons.  The empty list has no elements at all.
<P>
A list is notated by writing the elements of the list in order,
separated by blank space (space, tab, or return characters)
and surrounded by parentheses.
<P><pre>
(a b c)               ;A list of three symbols 
(2.0s0 (a 1) #\*)     ;A list of three things: a short floating-point 
                      ; number, another list, and a character object
<P>
</pre><P>
The empty list <tt>nil</tt> therefore can be written as <tt>()</tt>, because it is a list
with no elements.
<P>
A <i>dotted list</i> is one whose last cons does not have <tt>nil</tt> for
its <i>cdr</i>, rather some other data object (which is also not a cons,
or the first-mentioned cons would not be the last cons of the list).
Such a list is called ``dotted'' because of the special notation
used for it: the elements of the list are written between
parentheses as before, but after the last element and before
the right parenthesis are written a dot (surrounded by blank space)
and then the <i>cdr</i> of the last cons.  As a special case,
a single cons is notated by writing the <i>car</i> and the <i>cdr</i> between
parentheses and separated by a space-surrounded dot.
For example:
<P><pre>
(a . 4)         ;A cons whose <i>car</i> is a symbol 
                ; and whose <i>cdr</i> is an integer 
(a b c . d)     ;A dotted list with three elements whose last cons 
                ; has the symbol <tt>d</tt> in its <i>cdr</i>
</pre><P>
<P>
<hr>
<b>Compatibility note:</b> In MacLisp, the dot in dotted-list notation
need not be surrounded by white space or other delimiters.
The dot is required to be delimited in Common Lisp, as in Lisp Machine Lisp.
<hr>
<P>
It is legitimate to write something like <tt>(a b . (c d))</tt>;
this means the same as <tt>(a b c d)</tt>.  The standard Lisp
output routines will never print a list in the first form, however;
they will avoid dot notation wherever possible.
<P>
Often the term <i>list</i> is used to refer either to true lists or to
dotted lists.  When the distinction is important,
the term ``true list'' will be used to refer to a list
terminated by <tt>nil</tt>.  Most functions
advertised to operate on lists expect to be given true lists.  Throughout
this book, unless otherwise specified, it is an error to pass a dotted
list to a function that is specified to require a list as an argument.
<P>
<hr>
<b>Implementation note:</b> Implementors are encouraged to use the equivalent
of the predicate <tt>endp</tt> wherever it is necessary to test
for the end of a list.  Whenever feasible, this test should explicitly
signal an error if a list is found to be terminated by a non-<tt>nil</tt> atom.
However, such an explicit error signal is not required, because
some such tests occur in important loops where efficiency is important.
In such cases, the predicate <tt>atom</tt> may be used to test
for the end of the list, quietly treating any non-<tt>nil</tt> list-terminating
atom as if it were <tt>nil</tt>.
<hr>
<P>
Sometimes the term <i>tree</i> is used to refer to some cons
and all the other conses transitively accessible to it
through <i>car</i> and <i>cdr</i> links until non-conses are reached;
these non-conses are called the <i>leaves</i> of the tree.
<P>
Lists, dotted lists, and trees are not mutually exclusive data types;
they are simply useful points of view about structures of conses.
There are yet other terms, such as <i>association list</i>.
None of these are true Lisp data types.  Conses are a data type,
and <tt>nil</tt> is the sole object of type <tt>null</tt>.
The Lisp data type <tt>list</tt> is taken to mean the union of the
<tt>cons</tt> and <tt>null</tt> data types, and therefore encompasses both
true lists and dotted lists.
<P>
<BR> <HR><A NAME=tex2html1854 HREF="node29.html"><IMG ALIGN=BOTTOM ALT="next" SRC="icons/next_motif.gif"></A> <A NAME=tex2html1852 HREF="node15.html"><IMG ALIGN=BOTTOM ALT="up" SRC="icons/up_motif.gif"></A> <A NAME=tex2html1846 HREF="node27.html"><IMG ALIGN=BOTTOM ALT="previous" SRC="icons/previous_motif.gif"></A> <A NAME=tex2html1856 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="contents" SRC="icons/contents_motif.gif"></A> <A NAME=tex2html1857 HREF="index.html"><IMG ALIGN=BOTTOM ALT="index" SRC="icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME=tex2html1855 HREF="node29.html"> Arrays</A>
<B>Up:</B> <A NAME=tex2html1853 HREF="node15.html"> Data Types</A>
<B> Previous:</B> <A NAME=tex2html1847 HREF="node27.html"> Symbols</A>
<HR> <P>
<HR>
<P><ADDRESS>
AI.Repository@cs.cmu.edu
</ADDRESS>
</BODY>
