root/trunk/lispref/lists.texi

@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2001,
@c   2002, 2003, 2004, 2005, 2006, 2007, 2008  Free Software Foundation, Inc.
@c See the file elisp.texi for copying conditions.
@setfilename ../info/lists
@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
@chapter Lists
@cindex lists
@cindex element (of list)

  A @dfn{list} represents a sequence of zero or more elements (which may
be any Lisp objects).  The important difference between lists and
vectors is that two or more lists can share part of their structure; in
addition, you can insert or delete elements in a list without copying
the whole list.

@menu
* Cons Cells::          How lists are made out of cons cells.
* List-related Predicates::        Is this object a list?  Comparing two lists.
* List Elements::       Extracting the pieces of a list.
* Building Lists::      Creating list structure.
* List Variables::      Modifying lists stored in variables.
* Modifying Lists::     Storing new pieces into an existing list.
* Sets And Lists::      A list can represent a finite mathematical set.
* Association Lists::   A list can represent a finite relation or mapping.
* Rings::               Managing a fixed-size ring of objects.
@end menu

@node Cons Cells
@section Lists and Cons Cells
@cindex lists and cons cells

  Lists in Lisp are not a primitive data type; they are built up from
@dfn{cons cells}.  A cons cell is a data object that represents an
ordered pair.  That is, it has two slots, and each slot @dfn{holds}, or
@dfn{refers to}, some Lisp object.  One slot is known as the @sc{car},
and the other is known as the @sc{cdr}.  (These names are traditional;
see @ref{Cons Cell Type}.)  @sc{cdr} is pronounced ``could-er.''

  We say that ``the @sc{car} of this cons cell is'' whatever object
its @sc{car} slot currently holds, and likewise for the @sc{cdr}.

  A list is a series of cons cells ``chained together,'' so that each
cell refers to the next one.  There is one cons cell for each element of
the list.  By convention, the @sc{car}s of the cons cells hold the
elements of the list, and the @sc{cdr}s are used to chain the list: the
@sc{cdr} slot of each cons cell refers to the following cons cell.  The
@sc{cdr} of the last cons cell is @code{nil}.  This asymmetry between
the @sc{car} and the @sc{cdr} is entirely a matter of convention; at the
level of cons cells, the @sc{car} and @sc{cdr} slots have the same
characteristics.

@cindex true list
  Since @code{nil} is the conventional value to put in the @sc{cdr} of
the last cons cell in the list, we call that case a @dfn{true list}.

  In Lisp, we consider the symbol @code{nil} a list as well as a
symbol; it is the list with no elements.  For convenience, the symbol
@code{nil} is considered to have @code{nil} as its @sc{cdr} (and also
as its @sc{car}).  Therefore, the @sc{cdr} of a true list is always a
true list.

@cindex dotted list
@cindex circular list
  If the @sc{cdr} of a list's last cons cell is some other value,
neither @code{nil} nor another cons cell, we call the structure a
@dfn{dotted list}, since its printed representation would use
@samp{.}.  There is one other possibility: some cons cell's @sc{cdr}
could point to one of the previous cons cells in the list.  We call
that structure a @dfn{circular list}.

  For some purposes, it does not matter whether a list is true,
circular or dotted.  If the program doesn't look far enough down the
list to see the @sc{cdr} of the final cons cell, it won't care.
However, some functions that operate on lists demand true lists and
signal errors if given a dotted list.  Most functions that try to find
the end of a list enter infinite loops if given a circular list.

@cindex list structure
  Because most cons cells are used as part of lists, the phrase
@dfn{list structure} has come to mean any structure made out of cons
cells.

  The @sc{cdr} of any nonempty true list @var{l} is a list containing all the
elements of @var{l} except the first.

  @xref{Cons Cell Type}, for the read and print syntax of cons cells and
lists, and for ``box and arrow'' illustrations of lists.

@node List-related Predicates
@section Predicates on Lists

  The following predicates test whether a Lisp object is an atom,
whether it is a cons cell or is a list, or whether it is the
distinguished object @code{nil}.  (Many of these predicates can be
defined in terms of the others, but they are used so often that it is
worth having all of them.)

@defun consp object
This function returns @code{t} if @var{object} is a cons cell, @code{nil}
otherwise.  @code{nil} is not a cons cell, although it @emph{is} a list.
@end defun

@defun atom object
This function returns @code{t} if @var{object} is an atom, @code{nil}
otherwise.  All objects except cons cells are atoms.  The symbol
@code{nil} is an atom and is also a list; it is the only Lisp object
that is both.

@example
(atom @var{object}) @equiv{} (not (consp @var{object}))
@end example
@end defun

@defun listp object
This function returns @code{t} if @var{object} is a cons cell or
@code{nil}.  Otherwise, it returns @code{nil}.

@example
@group
(listp '(1))
     @result{} t
@end group
@group
(listp '())
     @result{} t
@end group
@end example
@end defun

@defun nlistp object
This function is the opposite of @code{listp}: it returns @code{t} if
@var{object} is not a list.  Otherwise, it returns @code{nil}.

@example
(listp @var{object}) @equiv{} (not (nlistp @var{object}))
@end example
@end defun

@defun null object
This function returns @code{t} if @var{object} is @code{nil}, and
returns @code{nil} otherwise.  This function is identical to @code{not},
but as a matter of clarity we use @code{null} when @var{object} is
considered a list and @code{not} when it is considered a truth value
(see @code{not} in @ref{Combining Conditions}).

@example
@group
(null '(1))
     @result{} nil
@end group
@group
(null '())
     @result{} t
@end group
@end example
@end defun


@node List Elements
@section Accessing Elements of Lists
@cindex list elements

@defun car cons-cell
This function returns the value referred to by the first slot of the
cons cell @var{cons-cell}.  Expressed another way, this function
returns the @sc{car} of @var{cons-cell}.

As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
is defined to return @code{nil}; therefore, any list is a valid argument
for @code{car}.  An error is signaled if the argument is not a cons cell
or @code{nil}.

@example
@group
(car '(a b c))
     @result{} a
@end group
@group
(car '())
     @result{} nil
@end group
@end example
@end defun

@defun cdr cons-cell
This function returns the value referred to by the second slot of
the cons cell @var{cons-cell}.  Expressed another way, this function
returns the @sc{cdr} of @var{cons-cell}.

As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
is defined to return @code{nil}; therefore, any list is a valid argument
for @code{cdr}.  An error is signaled if the argument is not a cons cell
or @code{nil}.

@example
@group
(cdr '(a b c))
     @result{} (b c)
@end group
@group
(cdr '())
     @result{} nil
@end group
@end example
@end defun

@defun car-safe object
This function lets you take the @sc{car} of a cons cell while avoiding
errors for other data types.  It returns the @sc{car} of @var{object} if
@var{object} is a cons cell, @code{nil} otherwise.  This is in contrast
to @code{car}, which signals an error if @var{object} is not a list.

@example
@group
(car-safe @var{object})
@equiv{}
(let ((x @var{object}))
  (if (consp x)
      (car x)
    nil))
@end group
@end example
@end defun

@defun cdr-safe object
This function lets you take the @sc{cdr} of a cons cell while
avoiding errors for other data types.  It returns the @sc{cdr} of
@var{object} if @var{object} is a cons cell, @code{nil} otherwise.
This is in contrast to @code{cdr}, which signals an error if
@var{object} is not a list.

@example
@group
(cdr-safe @var{object})
@equiv{}
(let ((x @var{object}))
  (if (consp x)
      (cdr x)
    nil))
@end group
@end example
@end defun

@defmac pop listname
This macro is a way of examining the @sc{car} of a list,
and taking it off the list, all at once.

It operates on the list which is stored in the symbol @var{listname}.
It removes this element from the list by setting @var{listname}
to the @sc{cdr} of its old value---but it also returns the @sc{car}
of that list, which is the element being removed.

@example
x
     @result{} (a b c)
(pop x)
     @result{} a
x
     @result{} (b c)
@end example
@end defmac

@defun nth n list
@anchor{Definition of nth}
This function returns the @var{n}th element of @var{list}.  Elements
are numbered starting with zero, so the @sc{car} of @var{list} is
element number zero.  If the length of @var{list} is @var{n} or less,
the value is @code{nil}.

If @var{n} is negative, @code{nth} returns the first element of
@var{list}.

@example
@group
(nth 2 '(1 2 3 4))
     @result{} 3
@end group
@group
(nth 10 '(1 2 3 4))
     @result{} nil
@end group
@group
(nth -3 '(1 2 3 4))
     @result{} 1

(nth n x) @equiv{} (car (nthcdr n x))
@end group
@end example

The function @code{elt} is similar, but applies to any kind of sequence.
For historical reasons, it takes its arguments in the opposite order.
@xref{Sequence Functions}.
@end defun

@defun nthcdr n list
This function returns the @var{n}th @sc{cdr} of @var{list}.  In other
words, it skips past the first @var{n} links of @var{list} and returns
what follows.

If @var{n} is zero or negative, @code{nthcdr} returns all of
@var{list}.  If the length of @var{list} is @var{n} or less,
@code{nthcdr} returns @code{nil}.

@example
@group
(nthcdr 1 '(1 2 3 4))
     @result{} (2 3 4)
@end group
@group
(nthcdr 10 '(1 2 3 4))
     @result{} nil
@end group
@group
(nthcdr -3 '(1 2 3 4))
     @result{} (1 2 3 4)
@end group
@end example
@end defun

@defun last list &optional n
This function returns the last link of @var{list}.  The @code{car} of
this link is the list's last element.  If @var{list} is null,
@code{nil} is returned.  If @var{n} is non-@code{nil}, the
@var{n}th-to-last link is returned instead, or the whole of @var{list}
if @var{n} is bigger than @var{list}'s length.
@end defun

@defun safe-length list
@anchor{Definition of safe-length}
This function returns the length of @var{list}, with no risk of either
an error or an infinite loop.  It generally returns the number of
distinct cons cells in the list.  However, for circular lists,
the value is just an upper bound; it is often too large.

If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
returns 0.
@end defun

  The most common way to compute the length of a list, when you are not
worried that it may be circular, is with @code{length}.  @xref{Sequence
Functions}.

@defun caar cons-cell
This is the same as @code{(car (car @var{cons-cell}))}.
@end defun

@defun cadr cons-cell
This is the same as @code{(car (cdr @var{cons-cell}))}
or @code{(nth 1 @var{cons-cell})}.
@end defun

@defun cdar cons-cell
This is the same as @code{(cdr (car @var{cons-cell}))}.
@end defun

@defun cddr cons-cell
This is the same as @code{(cdr (cdr @var{cons-cell}))}
or @code{(nthcdr 2 @var{cons-cell})}.
@end defun

@defun butlast x &optional n
This function returns the list @var{x} with the last element,
or the last @var{n} elements, removed.  If @var{n} is greater
than zero it makes a copy of the list so as not to damage the
original list.  In general, @code{(append (butlast @var{x} @var{n})
(last @var{x} @var{n}))} will return a list equal to @var{x}.
@end defun

@defun nbutlast x &optional n
This is a version of @code{butlast} that works by destructively
modifying the @code{cdr} of the appropriate element, rather than
making a copy of the list.
@end defun

@node Building Lists
@comment  node-name,  next,  previous,  up
@section Building Cons Cells and Lists
@cindex cons cells
@cindex building lists

  Many functions build lists, as lists reside at the very heart of Lisp.
@code{cons} is the fundamental list-building function; however, it is
interesting to note that @code{list} is used more times in the source
code for Emacs than @code{cons}.

@defun cons object1 object2
This function is the most basic function for building new list
structure.  It creates a new cons cell, making @var{object1} the
@sc{car}, and @var{object2} the @sc{cdr}.  It then returns the new
cons cell.  The arguments @var{object1} and @var{object2} may be any
Lisp objects, but most often @var{object2} is a list.

@example
@group
(cons 1 '(2))
     @result{} (1 2)
@end group
@group
(cons 1 '())
     @result{} (1)
@end group
@group
(cons 1 2)
     @result{} (1 . 2)
@end group
@end example

@cindex consing
@code{cons} is often used to add a single element to the front of a
list.  This is called @dfn{consing the element onto the list}.
@footnote{There is no strictly equivalent way to add an element to
the end of a list.  You can use @code{(append @var{listname} (list
@var{newelt}))}, which creates a whole new list by copying @var{listname}
and adding @var{newelt} to its end.  Or you can use @code{(nconc
@var{listname} (list @var{newelt}))}, which modifies @var{listname}
by following all the @sc{cdr}s and then replacing the terminating
@code{nil}.  Compare this to adding an element to the beginning of a
list with @code{cons}, which neither copies nor modifies the list.}
For example:

@example
(setq list (cons newelt list))
@end example

Note that there is no conflict between the variable named @code{list}
used in this example and the function named @code{list} described below;
any symbol can serve both purposes.
@end defun

@defun list &rest objects
This function creates a list with @var{objects} as its elements.  The
resulting list is always @code{nil}-terminated.  If no @var{objects}
are given, the empty list is returned.

@example
@group
(list 1 2 3 4 5)
     @result{} (1 2 3 4 5)
@end group
@group
(list 1 2 '(3 4 5) 'foo)
     @result{} (1 2 (3 4 5) foo)
@end group
@group
(list)
     @result{} nil
@end group
@end example
@end defun

@defun make-list length object
This function creates a list of @var{length} elements, in which each
element is @var{object}.  Compare @code{make-list} with
@code{make-string} (@pxref{Creating Strings}).

@example
@group
(make-list 3 'pigs)
     @result{} (pigs pigs pigs)
@end group
@group
(make-list 0 'pigs)
     @result{} nil
@end group
@group
(setq l (make-list 3 '(a b))
     @result{} ((a b) (a b) (a b))
(eq (car l) (cadr l))
     @result{} t
@end group
@end example
@end defun

@defun append &rest sequences
@cindex copying lists
This function returns a list containing all the elements of
@var{sequences}.  The @var{sequences} may be lists, vectors,
bool-vectors, or strings, but the last one should usually be a list.
All arguments except the last one are copied, so none of the arguments
is altered.  (See @code{nconc} in @ref{Rearrangement}, for a way to join
lists with no copying.)

More generally, the final argument to @code{append} may be any Lisp
object.  The final argument is not copied or converted; it becomes the
@sc{cdr} of the last cons cell in the new list.  If the final argument
is itself a list, then its elements become in effect elements of the
result list.  If the final element is not a list, the result is a
dotted list since its final @sc{cdr} is not @code{nil} as required
in a true list.

In Emacs 20 and before, the @code{append} function also allowed
integers as (non last) arguments.  It converted them to strings of
digits, making up the decimal print representation of the integer, and
then used the strings instead of the original integers.  This obsolete
usage no longer works.  The proper way to convert an integer to a
decimal number in this way is with @code{format} (@pxref{Formatting
Strings}) or @code{number-to-string} (@pxref{String Conversion}).
@end defun

  Here is an example of using @code{append}:

@example
@group
(setq trees '(pine oak))
     @result{} (pine oak)
(setq more-trees (append '(maple birch) trees))
     @result{} (maple birch pine oak)
@end group

@group
trees
     @result{} (pine oak)
more-trees
     @result{} (maple birch pine oak)
@end group
@group
(eq trees (cdr (cdr more-trees)))
     @result{} t
@end group
@end example

  You can see how @code{append} works by looking at a box diagram.  The
variable @code{trees} is set to the list @code{(pine oak)} and then the
variable @code{more-trees} is set to the list @code{(maple birch pine
oak)}.  However, the variable @code{trees} continues to refer to the
original list:

@smallexample
@group
more-trees                trees
|                           |
|     --- ---      --- ---   -> --- ---      --- ---
 --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
      --- ---      --- ---      --- ---      --- ---
       |            |            |            |
       |            |            |            |
        --> maple    -->birch     --> pine     --> oak
@end group
@end smallexample

  An empty sequence contributes nothing to the value returned by
@code{append}.  As a consequence of this, a final @code{nil} argument
forces a copy of the previous argument:

@example
@group
trees
     @result{} (pine oak)
@end group
@group
(setq wood (append trees nil))
     @result{} (pine oak)
@end group
@group
wood
     @result{} (pine oak)
@end group
@group
(eq wood trees)
     @result{} nil
@end group
@end example

@noindent
This once was the usual way to copy a list, before the function
@code{copy-sequence} was invented.  @xref{Sequences Arrays Vectors}.

  Here we show the use of vectors and strings as arguments to @code{append}:

@example
@group
(append [a b] "cd" nil)
     @result{} (a b 99 100)
@end group
@end example

  With the help of @code{apply} (@pxref{Calling Functions}), we can append
all the lists in a list of lists:

@example
@group
(apply 'append '((a b c) nil (x y z) nil))
     @result{} (a b c x y z)
@end group
@end example

  If no @var{sequences} are given, @code{nil} is returned:

@example
@group
(append)
     @result{} nil
@end group
@end example

  Here are some examples where the final argument is not a list:

@example
(append '(x y) 'z)
     @result{} (x y . z)
(append '(x y) [z])
     @result{} (x y . [z])
@end example

@noindent
The second example shows that when the final argument is a sequence but
not a list, the sequence's elements do not become elements of the
resulting list.  Instead, the sequence becomes the final @sc{cdr}, like
any other non-list final argument.

@defun reverse list
This function creates a new list whose elements are the elements of
@var{list}, but in reverse order.  The original argument @var{list} is
@emph{not} altered.

@example
@group
(setq x '(1 2 3 4))
     @result{} (1 2 3 4)
@end group
@group
(reverse x)
     @result{} (4 3 2 1)
x
     @result{} (1 2 3 4)
@end group
@end example
@end defun

@defun copy-tree tree &optional vecp
This function returns a copy of the tree @code{tree}.  If @var{tree} is a
cons cell, this makes a new cons cell with the same @sc{car} and
@sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
same way.

Normally, when @var{tree} is anything other than a cons cell,
@code{copy-tree} simply returns @var{tree}.  However, if @var{vecp} is
non-@code{nil}, it copies vectors too (and operates recursively on
their elements).
@end defun

@defun number-sequence from &optional to separation
This returns a list of numbers starting with @var{from} and
incrementing by @var{separation}, and ending at or just before
@var{to}.  @var{separation} can be positive or negative and defaults
to 1.  If @var{to} is @code{nil} or numerically equal to @var{from},
the value is the one-element list @code{(@var{from})}.  If @var{to} is
less than @var{from} with a positive @var{separation}, or greater than
@var{from} with a negative @var{separation}, the value is @code{nil}
because those arguments specify an empty sequence.

If @var{separation} is 0 and @var{to} is neither @code{nil} nor
numerically equal to @var{from}, @code{number-sequence} signals an
error, since those arguments specify an infinite sequence.

All arguments can be integers or floating point numbers.  However,
floating point arguments can be tricky, because floating point
arithmetic is inexact.  For instance, depending on the machine, it may
quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
the one element list @code{(0.4)}, whereas
@code{(number-sequence 0.4 0.8 0.2)} returns a list with three
elements.  The @var{n}th element of the list is computed by the exact
formula @code{(+ @var{from} (* @var{n} @var{separation}))}.  Thus, if
one wants to make sure that @var{to} is included in the list, one can
pass an expression of this exact type for @var{to}.  Alternatively,
one can replace @var{to} with a slightly larger value (or a slightly
more negative value if @var{separation} is negative).

Some examples:

@example
(number-sequence 4 9)
     @result{} (4 5 6 7 8 9)
(number-sequence 9 4 -1)
     @result{} (9 8 7 6 5 4)
(number-sequence 9 4 -2)
     @result{} (9 7 5)
(number-sequence 8)
     @result{} (8)
(number-sequence 8 5)
     @result{} nil
(number-sequence 5 8 -1)
     @result{} nil
(number-sequence 1.5 6 2)
     @result{} (1.5 3.5 5.5)
@end example
@end defun

@node List Variables
@section Modifying List Variables

  These functions, and one macro, provide convenient ways
to modify a list which is stored in a variable.

@defmac push newelt listname
This macro provides an alternative way to write
@code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.

@example
(setq l '(a b))
     @result{} (a b)
(push 'c l)
     @result{} (c a b)
l
     @result{} (c a b)
@end example
@end defmac

  Two functions modify lists that are the values of variables.

@defun add-to-list symbol element &optional append compare-fn
This function sets the variable @var{symbol} by consing @var{element}
onto the old value, if @var{element} is not already a member of that
value.  It returns the resulting list, whether updated or not.  The
value of @var{symbol} had better be a list already before the call.
@code{add-to-list} uses @var{compare-fn} to compare @var{element}
against existing list members; if @var{compare-fn} is @code{nil}, it
uses @code{equal}.

Normally, if @var{element} is added, it is added to the front of
@var{symbol}, but if the optional argument @var{append} is
non-@code{nil}, it is added at the end.

The argument @var{symbol} is not implicitly quoted; @code{add-to-list}
is an ordinary function, like @code{set} and unlike @code{setq}.  Quote
the argument yourself if that is what you want.
@end defun

Here's a scenario showing how to use @code{add-to-list}:

@example
(setq foo '(a b))
     @result{} (a b)

(add-to-list 'foo 'c)     ;; @r{Add @code{c}.}
     @result{} (c a b)

(add-to-list 'foo 'b)     ;; @r{No effect.}
     @result{} (c a b)

foo                       ;; @r{@code{foo} was changed.}
     @result{} (c a b)
@end example

  An equivalent expression for @code{(add-to-list '@var{var}
@var{value})} is this:

@example
(or (member @var{value} @var{var})
    (setq @var{var} (cons @var{value} @var{var})))
@end example

@defun add-to-ordered-list symbol element &optional order
This function sets the variable @var{symbol} by inserting
@var{element} into the old value, which must be a list, at the
position specified by @var{order}.  If @var{element} is already a
member of the list, its position in the list is adjusted according
to @var{order}.  Membership is tested using @code{eq}.
This function returns the resulting list, whether updated or not.

The @var{order} is typically a number (integer or float), and the
elements of the list are sorted in non-decreasing numerical order.

@var{order} may also be omitted or @code{nil}.  Then the numeric order
of @var{element} stays unchanged if it already has one; otherwise,
@var{element} has no numeric order.  Elements without a numeric list
order are placed at the end of the list, in no particular order.

Any other value for @var{order} removes the numeric order of @var{element}
if it already has one; otherwise, it is equivalent to @code{nil}.

The argument @var{symbol} is not implicitly quoted;
@code{add-to-ordered-list} is an ordinary function, like @code{set}
and unlike @code{setq}.  Quote the argument yourself if that is what
you want.

The ordering information is stored in a hash table on @var{symbol}'s
@code{list-order} property.
@end defun

Here's a scenario showing how to use @code{add-to-ordered-list}:

@example
(setq foo '())
     @result{} nil

(add-to-ordered-list 'foo 'a 1)     ;; @r{Add @code{a}.}
     @result{} (a)

(add-to-ordered-list 'foo 'c 3)     ;; @r{Add @code{c}.}
     @result{} (a c)

(add-to-ordered-list 'foo 'b 2)     ;; @r{Add @code{b}.}
     @result{} (a b c)

(add-to-ordered-list 'foo 'b 4)     ;; @r{Move @code{b}.}
     @result{} (a c b)

(add-to-ordered-list 'foo 'd)       ;; @r{Append @code{d}.}
     @result{} (a c b d)

(add-to-ordered-list 'foo 'e)       ;; @r{Add @code{e}}.
     @result{} (a c b e d)

foo                       ;; @r{@code{foo} was changed.}
     @result{} (a c b e d)
@end example

@node Modifying Lists
@section Modifying Existing List Structure
@cindex destructive list operations

  You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
primitives @code{setcar} and @code{setcdr}.  We call these ``destructive''
operations because they change existing list structure.

@cindex CL note---@code{rplaca} vs @code{setcar}
@quotation
@findex rplaca
@findex rplacd
@b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
@code{rplacd} to alter list structure; they change structure the same
way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
return the cons cell while @code{setcar} and @code{setcdr} return the
new @sc{car} or @sc{cdr}.
@end quotation

@menu
* Setcar::          Replacing an element in a list.
* Setcdr::          Replacing part of the list backbone.
                      This can be used to remove or add elements.
* Rearrangement::   Reordering the elements in a list; combining lists.
@end menu

@node Setcar
@subsection Altering List Elements with @code{setcar}

  Changing the @sc{car} of a cons cell is done with @code{setcar}.  When
used on a list, @code{setcar} replaces one element of a list with a
different element.

@defun setcar cons object
This function stores @var{object} as the new @sc{car} of @var{cons},
replacing its previous @sc{car}.  In other words, it changes the
@sc{car} slot of @var{cons} to refer to @var{object}.  It returns the
value @var{object}.  For example:

@example
@group
(setq x '(1 2))
     @result{} (1 2)
@end group
@group
(setcar x 4)
     @result{} 4
@end group
@group
x
     @result{} (4 2)
@end group
@end example
@end defun

  When a cons cell is part of the shared structure of several lists,
storing a new @sc{car} into the cons changes one element of each of
these lists.  Here is an example:

@example
@group
;; @r{Create two lists that are partly shared.}
(setq x1 '(a b c))
     @result{} (a b c)
(setq x2 (cons 'z (cdr x1)))
     @result{} (z b c)
@end group

@group
;; @r{Replace the @sc{car} of a shared link.}
(setcar (cdr x1) 'foo)
     @result{} foo
x1                           ; @r{Both lists are changed.}
     @result{} (a foo c)
x2
     @result{} (z foo c)
@end group

@group
;; @r{Replace the @sc{car} of a link that is not shared.}
(setcar x1 'baz)
     @result{} baz
x1                           ; @r{Only one list is changed.}
     @result{} (baz foo c)
x2
     @result{} (z foo c)
@end group
@end example

  Here is a graphical depiction of the shared structure of the two lists
in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
changes them both:

@example
@group
        --- ---        --- ---      --- ---
x1---> |   |   |----> |   |   |--> |   |   |--> nil
        --- ---        --- ---      --- ---
         |        -->   |            |
         |       |      |            |
          --> a  |       --> b        --> c
                 |
       --- ---   |
x2--> |   |   |--
       --- ---
        |
        |
         --> z
@end group
@end example

  Here is an alternative form of box diagram, showing the same relationship:

@example
@group
x1:
 --------------       --------------       --------------
| car   | cdr  |     | car   | cdr  |     | car   | cdr  |
|   a   |   o------->|   b   |   o------->|   c   |  nil |
|       |      |  -->|       |      |     |       |      |
 --------------  |    --------------       --------------
                 |
x2:              |
 --------------  |
| car   | cdr  | |
|   z   |   o----
|       |      |
 --------------
@end group
@end example

@node Setcdr
@subsection Altering the CDR of a List

  The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:

@defun setcdr cons object
This function stores @var{object} as the new @sc{cdr} of @var{cons},
replacing its previous @sc{cdr}.  In other words, it changes the
@sc{cdr} slot of @var{cons} to refer to @var{object}.  It returns the
value @var{object}.
@end defun

  Here is an example of replacing the @sc{cdr} of a list with a
different list.  All but the first element of the list are removed in
favor of a different sequence of elements.  The first element is
unchanged, because it resides in the @sc{car} of the list, and is not
reached via the @sc{cdr}.

@example
@group
(setq x '(1 2 3))
     @result{} (1 2 3)
@end group
@group
(setcdr x '(4))
     @result{} (4)
@end group
@group
x
     @result{} (1 4)
@end group
@end example

  You can delete elements from the middle of a list by altering the
@sc{cdr}s of the cons cells in the list.  For example, here we delete
the second element, @code{b}, from the list @code{(a b c)}, by changing
the @sc{cdr} of the first cons cell:

@example
@group
(setq x1 '(a b c))
     @result{} (a b c)
(setcdr x1 (cdr (cdr x1)))
     @result{} (c)
x1
     @result{} (a c)
@end group
@end example

  Here is the result in box notation:

@smallexample
@group
                   --------------------
                  |                    |
 --------------   |   --------------   |    --------------
| car   | cdr  |  |  | car   | cdr  |   -->| car   | cdr  |
|   a   |   o-----   |   b   |   o-------->|   c   |  nil |
|       |      |     |       |      |      |       |      |
 --------------       --------------        --------------
@end group
@end smallexample

@noindent
The second cons cell, which previously held the element @code{b}, still
exists and its @sc{car} is still @code{b}, but it no longer forms part
of this list.

  It is equally easy to insert a new element by changing @sc{cdr}s:

@example
@group
(setq x1 '(a b c))
     @result{} (a b c)
(setcdr x1 (cons 'd (cdr x1)))
     @result{} (d b c)
x1
     @result{} (a d b c)
@end group
@end example

  Here is this result in box notation:

@smallexample
@group
 --------------        -------------       -------------
| car  | cdr   |      | car  | cdr  |     | car  | cdr  |
|   a  |   o   |   -->|   b  |   o------->|   c  |  nil |
|      |   |   |  |   |      |      |     |      |      |
 --------- | --   |    -------------       -------------
           |      |
     -----         --------
    |                      |
    |    ---------------   |
    |   | car   | cdr   |  |
     -->|   d   |   o------
        |       |       |
         ---------------
@end group
@end smallexample

@node Rearrangement
@subsection Functions that Rearrange Lists
@cindex rearrangement of lists
@cindex modification of lists

  Here are some functions that rearrange lists ``destructively'' by
modifying the @sc{cdr}s of their component cons cells.  We call these
functions ``destructive'' because they chew up the original lists passed
to them as arguments, relinking their cons cells to form a new list that
is the returned value.

@ifnottex
  See @code{delq}, in @ref{Sets And Lists}, for another function
that modifies cons cells.
@end ifnottex
@iftex
   The function @code{delq} in the following section is another example
of destructive list manipulation.
@end iftex

@defun nconc &rest lists
@cindex concatenating lists
@cindex joining lists
This function returns a list containing all the elements of @var{lists}.
Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
@emph{not} copied.  Instead, the last @sc{cdr} of each of the
@var{lists} is changed to refer to the following list.  The last of the
@var{lists} is not altered.  For example:

@example
@group
(setq x '(1 2 3))
     @result{} (1 2 3)
@end group
@group
(nconc x '(4 5))
     @result{} (1 2 3 4 5)
@end group
@group
x
     @result{} (1 2 3 4 5)
@end group
@end example

   Since the last argument of @code{nconc} is not itself modified, it is
reasonable to use a constant list, such as @code{'(4 5)}, as in the
above example.  For the same reason, the last argument need not be a
list:

@example
@group
(setq x '(1 2 3))
     @result{} (1 2 3)
@end group
@group
(nconc x 'z)
     @result{} (1 2 3 . z)
@end group
@group
x
     @result{} (1 2 3 . z)
@end group
@end example

However, the other arguments (all but the last) must be lists.

A common pitfall is to use a quoted constant list as a non-last
argument to @code{nconc}.  If you do this, your program will change
each time you run it!  Here is what happens:

@smallexample
@group
(defun add-foo (x)            ; @r{We want this function to add}
  (nconc '(foo) x))           ;   @r{@code{foo} to the front of its arg.}
@end group

@group
(symbol-function 'add-foo)
     @result{} (lambda (x) (nconc (quote (foo)) x))
@end group

@group
(setq xx (add-foo '(1 2)))    ; @r{It seems to work.}
     @result{} (foo 1 2)
@end group
@group
(setq xy (add-foo '(3 4)))    ; @r{What happened?}
     @result{} (foo 1 2 3 4)
@end group
@group
(eq xx xy)
     @result{} t
@end group

@group
(symbol-function 'add-foo)
     @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
@end group
@end smallexample
@end defun

@defun nreverse list
@cindex reversing a list
  This function reverses the order of the elements of @var{list}.
Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
the @sc{cdr}s in the cons cells forming the list.  The cons cell that
used to be the last one in @var{list} becomes the first cons cell of the
value.

  For example:

@example
@group
(setq x '(a b c))
     @result{} (a b c)
@end group
@group
x
     @result{} (a b c)
(nreverse x)
     @result{} (c b a)
@end group
@group
;; @r{The cons cell that was first is now last.}
x
     @result{} (a)
@end group
@end example

  To avoid confusion, we usually store the result of @code{nreverse}
back in the same variable which held the original list:

@example
(setq x (nreverse x))
@end example

  Here is the @code{nreverse} of our favorite example, @code{(a b c)},
presented graphically:

@smallexample
@group
@r{Original list head:}                       @r{Reversed list:}
 -------------        -------------        ------------
| car  | cdr  |      | car  | cdr  |      | car | cdr  |
|   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
|      |      |   |  |      |   |  |   |  |     |   |  |
 -------------    |   --------- | -    |   -------- | -
                  |             |      |            |
                   -------------        ------------
@end group
@end smallexample
@end defun

@defun sort list predicate
@cindex stable sort
@cindex sorting lists
This function sorts @var{list} stably, though destructively, and
returns the sorted list.  It compares elements using @var{predicate}.  A
stable sort is one in which elements with equal sort keys maintain their
relative order before and after the sort.  Stability is important when
successive sorts are used to order elements according to different
criteria.

The argument @var{predicate} must be a function that accepts two
arguments.  It is called with two elements of @var{list}.  To get an
increasing order sort, the @var{predicate} should return non-@code{nil} if the
first element is ``less than'' the second, or @code{nil} if not.

The comparison function @var{predicate} must give reliable results for
any given pair of arguments, at least within a single call to
@code{sort}.  It must be @dfn{antisymmetric}; that is, if @var{a} is
less than @var{b}, @var{b} must not be less than @var{a}.  It must be
@dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
is less than @var{c}, then @var{a} must be less than @var{c}.  If you
use a comparison function which does not meet these requirements, the
result of @code{sort} is unpredictable.

The destructive aspect of @code{sort} is that it rearranges the cons
cells forming @var{list} by changing @sc{cdr}s.  A nondestructive sort
function would create new cons cells to store the elements in their
sorted order.  If you wish to make a sorted copy without destroying the
original, copy it first with @code{copy-sequence} and then sort.

Sorting does not change the @sc{car}s of the cons cells in @var{list};
the cons cell that originally contained the element @code{a} in
@var{list} still has @code{a} in its @sc{car} after sorting, but it now
appears in a different position in the list due to the change of
@sc{cdr}s.  For example:

@example
@group
(setq nums '(1 3 2 6 5 4 0))
     @result{} (1 3 2 6 5 4 0)
@end group
@group
(sort nums '<)
     @result{} (0 1 2 3 4 5 6)
@end group
@group
nums
     @result{} (1 2 3 4 5 6)
@end group
@end example

@noindent
@strong{Warning}: Note that the list in @code{nums} no longer contains
0; this is the same cons cell that it was before, but it is no longer
the first one in the list.  Don't assume a variable that formerly held
the argument now holds the entire sorted list!  Instead, save the result
of @code{sort} and use that.  Most often we store the result back into
the variable that held the original list:

@example
(setq nums (sort nums '<))
@end example

@xref{Sorting}, for more functions that perform sorting.
See @code{documentation} in @ref{Accessing Documentation}, for a
useful example of @code{sort}.
@end defun

@node Sets And Lists
@section Using Lists as Sets
@cindex lists as sets
@cindex sets

  A list can represent an unordered mathematical set---simply consider a
value an element of a set if it appears in the list, and ignore the
order of the list.  To form the union of two sets, use @code{append} (as
long as you don't mind having duplicate elements).  You can remove
@code{equal} duplicates using @code{delete-dups}.  Other useful
functions for sets include @code{memq} and @code{delq}, and their
@code{equal} versions, @code{member} and @code{delete}.

@cindex CL note---lack @code{union}, @code{intersection}
@quotation
@b{Common Lisp note:} Common Lisp has functions @code{union} (which