comparison lispref/lists.texi @ 7118:08d61ef58d13

*** empty log message ***

7117:f1b6a927a442

@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; @sc{cdr} is
pronounced ``could-er.''

  A list is a series of cons cells chained together, one cons cell per
element of the list.  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.  For convenience, the symbol @code{nil} is
considered to have @code{nil} as its @sc{cdr} (and also as its
@sc{car}).

            |       |      |     |         |      |
             --------------       ----------------
@end group
@end example

  @xref{List Type}, for the read and print syntax of lists, and for more
``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, is a

@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

@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, or strings.
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:

@example
@group
(setq trees '(pine oak))
     @result{} (pine oak)

(eq trees (cdr (cdr more-trees)))
     @result{} t
@end group
@end example

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:

@smallexample
@group
more-trees                trees
|                           |

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

See @code{nconc} in @ref{Rearrangement}, for a way to join lists with no
copying.

Integers are also allowed as arguments to @code{append}.  They are
converted to strings of digits making up the decimal print
representation of the integer, and these strings are then appended.
Here's what happens:

@end menu

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

  Changing the @sc{car} of a cons cell is done with @code{setcar}, which
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:

@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 @sc{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

  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, to produce a new list that is the returned value.

@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

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

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:

@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
@section Using Lists as Sets
@cindex lists as sets
@cindex sets

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
@group
(memq 2 '(1 2 3 2 1))
     @result{} (2 3 2 1)
@end group
@group
(memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
     @result{} nil
@end group

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

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

Note that @code{(delq 2 sample-list)} modifies @code{sample-list} to
splice out the second element, but @code{(delq 1 sample-list)} does not
splice anything---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:

and the @code{(4)} in the @code{sample-list} are not @code{eq}:

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

The following two functions are like @code{memq} and @code{delq} but use
@code{equal} rather than @code{eq} to compare elements.  They are new in

     @result{} acorns
(assoc 'birch trees)
     @result{} nil
@end smallexample

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

@smallexample
(setq needles-per-cluster
      '((2 "Austrian Pine" "Red Pine")
        (3 "Pitch Pine")

@smallexample
@group
(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 group
@end smallexample
@end defun

7118:08d61ef58d13

@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 that 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; see
@ref{Cons Cell Type}.  @sc{cdr} is pronounced ``could-er.''

  A list is a series of cons cells chained together, one cons cell per
element of the list.  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.

@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 symbol @code{nil} is considered 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}).

            |       |      |     |         |      |
             --------------       ----------------
@end group
@end example

  @xref{Cons Cell Type}, for the read and print syntax of cons cells and
lists, and for more ``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, is a

@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
that is both.

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

@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, or strings,
but the last one should be a list.  All arguments except the last one
are copied, so none of them are altered.

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.

See @code{nconc} in @ref{Rearrangement}, for a way to join lists with no
copying.

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

@example
@group
(setq trees '(pine oak))
     @result{} (pine oak)

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

(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.

Integers are also allowed as arguments to @code{append}.  They are
converted to strings of digits making up the decimal print
representation of the integer, and these strings are then appended.
Here's what happens:

@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}.  It returns the value @var{object}.
For example:

@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}.  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

  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, to produce a new list that is the returned value.

@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

@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

@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 cell of the
value.

  For example:

@example
@group

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};
each cons cell in the result contains the same element that it contained
before.  The result differs from the argument @var{list} because the
cells themselves have been reordered.

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:

@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

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
@group
(memq 'b '(a b c b a))
     @result{} (b c b a)
@end group
@group
(memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
     @result{} nil
@end group

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

@example
@group
(setq sample-list '(a b c (4)))
     @result{} (a b c (4))
@end group
@group
(delq 'a sample-list)
     @result{} (b c (4))
@end group
@group
sample-list
     @result{} (a b c (4))
@end group
@group
(delq 'c sample-list)
     @result{} (a c (4))
@end group
@group
sample-list
     @result{} (a c (4))
@end group
@end example

Note that @code{(delq 'b sample-list)} modifies @code{sample-list} to
splice out the second element, but @code{(delq 'a sample-list)} does not
splice anything---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:

and the @code{(4)} in the @code{sample-list} are not @code{eq}:

@example
@group
(delq '(4) sample-list)
     @result{} (a c (4))
@end group
@end example

The following two functions are like @code{memq} and @code{delq} but use
@code{equal} rather than @code{eq} to compare elements.  They are new in

     @result{} acorns
(assoc 'birch trees)
     @result{} nil
@end smallexample

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

@smallexample
(setq needles-per-cluster
      '((2 "Austrian Pine" "Red Pine")
        (3 "Pitch Pine")

@smallexample
@group
(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 group
@end example

  This example shows how @code{copy-alist} makes it possible to change
the associations of one copy without affecting the other:

@example
@group
(setcdr (assq 3 needles-per-cluster)
        '("Martian Vacuum Pine"))
(cdr (assq 3 needles-per-cluster))
     @result{} ("Pitch Pine")
@end group
@end smallexample
@end defun