@c -*-texinfo-*-
@setfilename ../info/lists
@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
@chapter Lists
@cindex list
@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.
* Lists as Boxes::                 Graphical notation to explain lists.
* List-related Predicates::        Is this object a list?  Comparing two lists.
* List Elements::       Extracting the pieces of a list.
* Building Lists::      Creating list structure.
* 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.
@end menu

@node Cons Cells, Lists as Boxes, Lists, Lists
@section Lists and Cons Cells
@cindex lists and cons cells
@cindex @code{nil} and lists

  Lists in Lisp are not a primitive data type; they are built up from
@dfn{cons cells}.  A cons cell is a data object which represents an ordered
pair.  It records two Lisp objects, one labeled as the @sc{car}, and the
other labeled as the @sc{cdr}.  (These names are traditional.)

  A list is made by chaining cons cells together, one cons cell per
element.  By convention, the @sc{car}s of the cons cells are the
elements of the list, and the @sc{cdr}s are used to chain the list: the
@sc{cdr} of each cons cell is 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.

  The symbol @code{nil} is considered a list as well as a symbol; it is
the list with no elements.  Therefore, the @sc{cdr} of any nonempty list
@var{l} is a list containing all the elements of @var{l} except the
first.  For convenience, the symbol @code{nil} is considered to have
@code{nil} as its @sc{cdr} (and also as its @sc{car}).

@node Lists as Boxes, List-related Predicates, Cons Cells, Lists
@comment  node-name,  next,  previous,  up
@section Lists as Linked Pairs of Boxes
@cindex box representation for lists
@cindex lists represented as boxes
@cindex cons cell as box

  A cons cell can be illustrated as a pair of boxes.  The first box
represents the @sc{car} and the second box represents the @sc{cdr}.
Here is an illustration of the two-element list, @code{(tulip lily)},
made from two cons cells:

@group
@example
 ---------------         ---------------
|car    |cdr    |       |car    |cdr    |
| tulip |   o---------->| lily  |  nil  |
|       |       |       |       |       |
 ---------------         ---------------
@end example
@end group

  Each pair of boxes represents a cons cell.  Each box ``refers to'',
``points to'' or ``contains'' a Lisp object.  (These terms are
synonymous.)  The first box, which is the @sc{car} of the first cons
cell, contains the symbol @code{tulip}.  The arrow from the @sc{cdr} of
the first cons cell to the second cons cell indicates that the @sc{cdr}
of the first cons cell points to the second cons cell.

  The same list can be illustrated in a different sort of box notation
like this:

@group
@example
    ___ ___      ___ ___
   |___|___|--> |___|___|--> nil
     |            |
     |            |
      --> tulip    --> lily
@end example
@end group

  Here is a more complex illustration, this time of the three-element
list, @code{((pine needles) oak maple)}, the first element of which is
a two-element list:

@group
@example
    ___ ___      ___ ___      ___ ___
   |___|___|--> |___|___|--> |___|___|--> nil
     |            |            |
     |            |            |
     |             --> oak      --> maple
     |
     |     ___ ___      ___ ___
      --> |___|___|--> |___|___|--> nil
            |            |
            |            |
             --> pine     --> needles
@end example
@end group

  The same list is represented in the first box notation like this:

@group
@example
 ---------------         ---------------         ---------------
|car    |cdr    |       |car    |cdr    |       |car    |cdr    |
|   o   |   o---------->|  oak  |   o---------->| maple |  nil  |
|   |   |       |       |       |       |       |       |       |
 -- | ----------         ---------------         ---------------
    |
    |
    |        ---------------         -----------------
    |       |car    |cdr    |       |car      |cdr    |
     ------>| pine  |   o---------->| needles |  nil  |
            |       |       |       |         |       |
             ---------------         -----------------
@end example
@end group

  @xref{List Type}, for the read and print syntax of lists, and for more
``box and arrow'' illustrations of lists.

@node List-related Predicates, List Elements, Lists as Boxes, Lists
@section Predicates on Lists

The following predicates test whether a Lisp object is an atom, is a cons
cell or is a list, or whether it is the distinguished object @code{nil}.
(Many of these tests 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
@cindex atoms
  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
which 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
(listp '(1))
     @result{} t
(listp '())
     @result{} t
@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
(null '(1))
     @result{} nil
(null '())
     @result{} t
@end example
@end defun

@node List Elements, Building Lists, List-related Predicates, Lists
@section Accessing Elements of Lists
@cindex list elements

@defun car cons-cell
  This function returns the value pointed to by the first pointer 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
(car '(a b c))
     @result{} a
(car '())
     @result{} nil
@end example
@end defun

@defun cdr cons-cell
  This function returns the value pointed to by the second pointer 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
(cdr '(a b c))
     @result{} (b c)
(cdr '())
     @result{} nil
@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
(car-safe @var{object})
@equiv{}
(let ((x @var{object}))
  (if (consp x)
      (car x)
    nil))
@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
(cdr-safe @var{object})
@equiv{}
(let ((x @var{object}))
  (if (consp x)
      (cdr x)
    nil))
@end example
@end defun

@defun nth n list
  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 less than zero, then the first element is returned.

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

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

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

If @var{n} is less than or equal to zero, then all of @var{list} is
returned.  If the length of @var{list} is @var{n} or less, the value is
@code{nil}.

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

@node Building Lists, Modifying Lists, List Elements, 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 fundamental function used to build 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
(cons 1 '(2))
     @result{} (1 2)
(cons 1 '())
     @result{} (1)
(cons 1 2)
     @result{} (1 . 2)
@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}.  For
example:

@example
(setq list (cons newelt list))
@end example
@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
(list 1 2 3 4 5)
     @result{} (1 2 3 4 5)
(list 1 2 '(3 4 5) 'foo)
     @result{} (1 2 (3 4 5) foo)
@group
(list)
     @result{} nil
@end group
@end example
@end defun

@defun make-list length object
  This function creates a list of length @var{length}, in which all the
elements have the identical value @var{object}.  Compare
@code{make-list} with @code{make-string} (@pxref{Creating Strings}).

@example
(make-list 3 'pigs)
     @result{} (pigs pigs pigs)
(make-list 0 'pigs)
     @result{} nil
@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, strings, or
integers.  All arguments except the last one are copied, so none of them
are altered.

  The final argument to @code{append} may be any object but it is
typically a list.  The final argument is not copied or converted; it
becomes part of the structure of the new list.

  Here is an example:

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

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

  You can see what happens 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:

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

  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.

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

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

With the help of @code{apply}, we can append all the lists in a list of
lists:

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

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

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

In the special case where one of the @var{sequences} is an integer
(not a sequence of integers), it is first converted to a string of
digits making up the decimal print representation of the integer.  This
special case exists for compatibility with Mocklisp, and we don't
recommend you take advantage of it.  If you want to convert an integer
in this way, use @code{format} (@pxref{Formatting Strings}) or
@code{int-to-string} (@pxref{String Conversion}).

@group
@example
(setq trees '(pine oak))
     @result{} (pine oak)
(char-to-string ?\054)
     @result{} "6"
(setq longer-list (append trees 6 '(spruce)))
     @result{} (pine oak 54 spruce)
(setq x-list (append trees 6 6))
     @result{} (pine oak 54 . 6)
@end example
@end group

See @code{nconc} in @ref{Rearrangement}, for another way to join lists
without copying.
@end defun

@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
(setq x '(1 2 3 4))
     @result{} (1 2 3 4)
(reverse x)
     @result{} (4 3 2 1)
x
     @result{} (1 2 3 4)
@end example
@end defun

@node Modifying Lists, Sets And Lists, Building Lists, Lists
@section Modifying Existing List Structure

  You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
primitives @code{setcar} and @code{setcdr}.

@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, Setcdr, Modifying Lists, Modifying Lists
@subsection Altering List Elements with @code{setcar}

  Changing the @sc{car} of a cons cell is done with @code{setcar} and
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}.  It returns the value @var{object}.
For example:

@example
(setq x '(1 2))
     @result{} (1 2)
(setcar x '4)
     @result{} 4
x
     @result{} (4 2)
@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
;; @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)

;; @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)

;; @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 example

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

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

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

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

@node Setcdr, Rearrangement, Setcar, Modifying Lists
@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} into the cdr of @var{cons}.  The
value returned is @var{object}, not @var{cons}.
@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
(setq x '(1 2 3))
     @result{} (1 2 3)
(setcdr x '(4))
     @result{} (4)
@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 cell:

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

Here is the result in box notation:

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

@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
(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 example

  Here is this result in box notation:

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

@node Rearrangement,  , Setcdr, Modifying Lists
@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 the original lists passed as arguments
to them are chewed up to produce a new list that is subsequently
returned.

@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
(setq x '(1 2 3))
     @result{} (1 2 3)
(nconc x '(4 5))
     @result{} (1 2 3 4 5)
x
     @result{} (1 2 3 4 5)
@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 is done in
the above example.  For the same reason, the last argument need not be a
list:

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

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:

@example
(defun add-foo (x)                ; @r{This function should add}
  (nconc '(foo) x))               ; @r{@code{foo} to the front of its arg.}

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

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

(symbol-function 'add-foo)
     @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
@end example
@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 destructively
by reversing the @sc{cdr}s in the cons cells forming the list.  The cons
cell which used to be the last one in @var{list} becomes the first cell
of the value.

  For example:

@example
(setq x '(1 2 3 4))
     @result{} (1 2 3 4)
x
     @result{} (1 2 3 4)
(nreverse x)
     @result{} (4 3 2 1)
;; @r{The cell that was first is now last.}
x
     @result{} (1)
@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:

@group
@example
@r{Original list head:}                                 @r{Reversed list:}
 ---------------         ---------------         ---------------
|car    |cdr    |       |car    |cdr    |       |car    |cdr    |
|   a   |  nil  |<--    |   b   |   o   |<--    |   c   |   o   |
|       |       |   |   |       |   |   |   |   |       |   |   |
 ---------------    |    ---------- | --    |    ---------- | --
                    |               |       |               |
                     ---------------         ---------------
@end example
@end group
@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 @code{t} if the
first element is ``less than'' the second, or @code{nil} if not.

  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 sort a list without destroying the
original, copy it first with @code{copy-sequence}.

  The @sc{car}s of the cons cells are not changed; 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
(setq nums '(1 3 2 6 5 4 0))
     @result{} (1 3 2 6 5 4 0)
(sort nums '<)
     @result{} (0 1 2 3 4 5 6)
nums
     @result{} (1 2 3 4 5 6)
@end example

@noindent
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

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

@node Sets And Lists, Association Lists, Modifying Lists, 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).  Two other useful
functions for sets are @code{memq} and @code{delq}.

@quotation
@b{Common Lisp note:} Common Lisp has functions @code{union} (which
avoids duplicate elements) and @code{intersection} for set operations,
but GNU Emacs Lisp does not have them.  You can write them in Lisp if
you wish.
@end quotation

@defun memq object list
@cindex membership in a list
  This function tests to see whether @var{object} is a member of
@var{list}.  If it is, @code{memq} returns a list starting with the
first occurrence of @var{object}.  Otherwise, it returns @code{nil}.
The letter @samp{q} in @code{memq} says that it uses @code{eq} to
compare @var{object} against the elements of the list.  For example:

@example
(memq 2 '(1 2 3 2 1))
     @result{} (2 3 2 1)
(memq '(2) '((1) (2)))   ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
     @result{} nil
@end example
@end defun

@defun delq object list
@cindex deletion of elements
  This function removes all elements @code{eq} to @var{object} from
@var{list}.

Elements at the front of the list are removed (when necessary) simply
by advancing down the list and returning a sublist that starts after
those elements:

@example
(delq 'a '(a b c))
@equiv{}
(cdr '(a b c))
@end example

When an element to be deleted appears in the middle of the list,
removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).

@example
(setq sample-list '(1 2 3 (4)))
     @result{} (1 2 3 (4))
(delq 1 sample-list)
     @result{} (2 3 (4))
sample-list
     @result{} (1 2 3 (4))
(delq 2 sample-list)
     @result{} (1 3 (4))
sample-list
     @result{} (1 3 (4))
@end example

Note that @code{(delq 2 sample-list)} removes the second element of
@code{sample-list}, but @code{(delq 1 sample-list)} does not remove the
first element---it just returns a shorter list.  Don't assume that a
variable which formerly held the argument @var{list} now has fewer
elements, or that it still holds the original list!  Instead, save the
result of @code{delq} and use that.  Most often we store the result back
into the variable that held the original list:

@example
(setq flowers (delq 'rose flowers))
@end example

In the following example, the @code{(4)} that @code{delq} attempts to match
and the @code{(4)} in the @code{sample-list} are not @code{eq}:

@example
(delq '(4) sample-list)
     @result{} (1 3 (4))
@end example
@end defun

@node Association Lists,  , Sets And Lists, Lists
@section Association Lists
@cindex association list
@cindex alist

  An @dfn{association list}, or @dfn{alist} for short, records a mapping
from keys to values.  It is a list of cons cells called
@dfn{associations}: the @sc{car} of each cell is the @dfn{key}, and the
@sc{cdr} is the @dfn{associated value}.  (This usage of ``key'' is not
related to the term ``key sequence''; it means any object which can be
looked up in a table.)

  Here is an example of an alist.  The key @code{pine} is associated with
the value @code{cones}; the key @code{oak} is associated with
@code{acorns}; and the key @code{maple} is associated with @code{seeds}.

@example
'((pine . cones)
  (oak . acorns)
  (maple . seeds))
@end example

  The associated values in an alist may be any Lisp objects; so may the
keys.  For example, in the following alist, the symbol @code{a} is
associated with the number @code{1}, and the string @code{"b"} is
associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
the alist element:

@example
((a . 1) ("b" 2 3))
@end example

  Sometimes it is better to design an alist to store the associated
value in the @sc{car} of the @sc{cdr} of the element.  Here is an
example:

@example
'((rose red) (lily white) (buttercup yellow)))
@end example

@noindent
Here we regard @code{red} as the value associated with @code{rose}.  One
advantage of this method is that you can store other related
information---even a list of other items---in the @sc{cdr} of the
@sc{cdr}.  One disadvantage is that you cannot use @code{rassq} (see
below) to find the element containing a given value.  When neither of
these considerations is important, the choice is a matter of taste, as
long as you are consistent about it for any given alist.

  Note that the same alist shown above could be regarded as having the
associated value in the @sc{cdr} of the element; the the value
associated with @code{rose} would be the list @code{(red)}.

  Association lists are often used to record information that you might
otherwise keep on a stack, since new associations may be added easily to
the front of the list.  When searching an association list for an
association with a given key, the first one found is returned, if there
is more than one.

  In Emacs Lisp, it is @emph{not} an error if an element of an
association list is not a cons cell.  The alist search functions simply
ignore such elements.  Many other versions of Lisp signal errors in such
cases.

  Note that property lists are similar to association lists in several
respects.  A property list behaves like an association list in which
each key can occur only once.  @xref{Property Lists}, for a comparison
of property lists and association lists.

@defun assoc key alist
  This function returns the first association for @var{key} in
@var{alist}.  It compares @var{key} against the alist elements using
@code{equal} (@pxref{Equality Predicates}).  It returns @code{nil} if no
association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
For example:

@example
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     @result{} ((pine . cones) (oak . acorns) (maple . seeds))
(assoc 'oak trees)
     @result{} (oak . acorns)
(cdr (assoc 'oak trees))
     @result{} acorns
(assoc 'birch trees)
     @result{} nil
@end example

Here is another example in which the keys and values are not symbols:

@example
(setq needles-per-cluster
      '((2 . ("Austrian Pine" "Red Pine"))
        (3 . "Pitch Pine")
        (5 . "White Pine")))

(cdr (assoc 3 needles-per-cluster))
     @result{} "Pitch Pine"
(cdr (assoc 2 needles-per-cluster))
     @result{} ("Austrian Pine" "Red Pine")
@end example
@end defun

@defun assq key alist
  This function is like @code{assoc} in that it returns the first
association for @var{key} in @var{alist}, but it makes the comparison
using @code{eq} instead of @code{equal}.  @code{assq} returns @code{nil}
if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
This function is used more often than @code{assoc}, since @code{eq} is
faster than @code{equal} and most alists use symbols as keys.
@xref{Equality Predicates}.

@example
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))

(assq 'pine trees)
     @result{} (pine . cones)
@end example

On the other hand, @code{assq} is not usually useful in alists where the
keys may not be symbols:

@example
(setq leaves
      '(("simple leaves" . oak)
        ("compound leaves" . horsechestnut)))

(assq "simple leaves" leaves)
     @result{} nil
(assoc "simple leaves" leaves)
     @result{} ("simple leaves" . oak)
@end example
@end defun

@defun rassq alist value
  This function returns the first association with value @var{value} in
@var{alist}.  It returns @code{nil} if no association in @var{alist} has
a @sc{cdr} @code{eq} to @var{value}.

  @code{rassq} is like @code{assq} except that the @sc{cdr} of the
@var{alist} associations is tested instead of the @sc{car}.  You can
think of this as ``reverse @code{assq}'', finding the key for a given
value.

  For example:

@example
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))

(rassq 'acorns trees)
     @result{} (oak . acorns)
(rassq 'spores trees)
     @result{} nil
@end example

Note that @code{rassq} cannot be used to search for a value stored in
the @sc{car} of the @sc{cdr} of an element:

@example
(setq colors '((rose red) (lily white) (buttercup yellow)))

(rassq 'white colors)
     @result{} nil
@end example

In this case, the @sc{cdr} of the association @code{(lily white)} is not
the symbol @code{white}, but rather the list @code{(white)}.  This can
be seen more clearly if the association is written in dotted pair
notation:

@example
(lily white) @equiv{} (lily . (white))
@end example
@end defun

@defun copy-alist alist
@cindex copying alists
This function returns a two-level deep copy of @var{alist}: it creates a
new copy of each association, so that you can alter the associations of
the new alist without changing the old one.

@example
(setq needles-per-cluster
      '((2 . ("Austrian Pine" "Red Pine"))
        (3 . "Pitch Pine")
        (5 . "White Pine")))
@result{}
((2 "Austrian Pine" "Red Pine")
 (3 . "Pitch Pine")
 (5 . "White Pine"))

(setq copy (copy-alist needles-per-cluster))
@result{}
((2 "Austrian Pine" "Red Pine")
 (3 . "Pitch Pine")
 (5 . "White Pine"))

(eq needles-per-cluster copy)
     @result{} nil
(equal needles-per-cluster copy)
     @result{} t
(eq (car needles-per-cluster) (car copy))
     @result{} nil
(cdr (car (cdr needles-per-cluster)))
     @result{} "Pitch Pine"
(eq (cdr (car (cdr needles-per-cluster)))
    (cdr (car (cdr copy))))
     @result{} t
@end example
@end defun


