@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998 Free Software Foundation, Inc.
+@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999
+@c 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
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 holds, or ``points to,'' 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
+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.
@end example
Each pair of boxes represents a cons cell. Each box ``refers to'',
-``points to'' or ``contains'' a Lisp object. (These terms are
+``points to'' or ``holds'' a Lisp object. (These terms are
synonymous.) The first box, which describes the @sc{car} of the first
cons cell, contains the symbol @code{tulip}. The arrow from the
@sc{cdr} box of the first cons cell to the second cons cell indicates
@cindex list elements
@defun car cons-cell
-This function returns the value pointed to by the first pointer of the
+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}.
@end defun
@defun cdr cons-cell
-This function returns the value pointed to by the second pointer of
+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}.
@end example
@end defun
+@tindex pop
+@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 is new in Emacs 21.
+
+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
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
@end example
@end defun
+@defun last list &optional n
+This function reruns the last link of the given @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-nil the
+@var{n}-th-to-last link is returned instead, or the whole @var{list} if
+@var{n} is bigger than @var{list}'s length.
+@end defun
+
@defun safe-length list
-@tindex safe-length
This function returns the length of @var{list}, with no risk
of either an error or an infinite loop.
Functions}.
@defun caar cons-cell
-@tindex caar
This is the same as @code{(car (car @var{cons-cell}))}.
@end defun
@defun cadr cons-cell
-@tindex cadr
This is the same as @code{(car (cdr @var{cons-cell}))}
or @code{(nth 1 @var{cons-cell})}.
@end defun
@defun cdar cons-cell
-@tindex cdar
This is the same as @code{(cdr (car @var{cons-cell}))}.
@end defun
@defun cddr cons-cell
-@tindex cddr
This is the same as @code{(cdr (cdr @var{cons-cell}))}
or @code{(nthcdr 2 @var{cons-cell})}.
@end defun
@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:
+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))
any symbol can serve both purposes.
@end defun
+@tindex push
+@defmac push newelt listname
+This macro provides an alternative way to write
+@code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
+It is new in Emacs 21.
+@end defmac
+
@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}
``dotted list'' since its final @sc{cdr} is not @code{nil} as required
in a true list.
-Here is an example of using @code{append}:
+The @code{append} function also allows integers as arguments. It
+converts them to strings of digits, making up the decimal print
+representation of the integer, and then uses the strings instead of the
+original integers. @strong{Don't use this feature; we plan to eliminate
+it. If you already use this feature, change your programs now!} 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
@end group
@end example
-You can see how @code{append} works by looking at a box diagram. The
+ 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
@end group
@end smallexample
-An empty sequence contributes nothing to the value returned by
+ 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.
+forces a copy of the previous argument:
@example
@group
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}:
+ Here we show the use of vectors and strings as arguments to @code{append}:
@example
@group
@end group
@end example
-With the help of @code{apply} (@pxref{Calling Functions}), we can append
+ With the help of @code{apply} (@pxref{Calling Functions}), we can append
all the lists in a list of lists:
@example
@end group
@end example
-If no @var{sequences} are given, @code{nil} is returned:
+ If no @var{sequences} are given, @code{nil} is returned:
@example
@group
@end group
@end example
-Here are some examples where the final argument is not a list:
+ Here are some examples where the final argument is not a list:
@example
(append '(x y) 'z)
resulting list. Instead, the sequence becomes the final @sc{cdr}, like
any other non-list final argument.
-The @code{append} function also allows integers as arguments. It
-converts them to strings of digits, making up the decimal print
-representation of the integer, and then uses the strings instead of the
-original integers. @strong{Don't use this feature; we plan to eliminate
-it. If you already use this feature, change your programs now!} 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
-
@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
@end example
@end defun
+@defun remq object list
+This function returns a copy of @var{list}, with all elements removed
+which are @code{eq} to @var{object}. The letter @samp{q} in @code{remq}
+says that it uses @code{eq} to compare @var{object} against the elements
+of @code{list}.
+
+@example
+@group
+(setq sample-list '(a b c a b c))
+ @result{} (a b c a b c)
+@end group
+@group
+(remq 'a sample-list)
+ @result{} (b c b c)
+@end group
+@group
+sample-list
+ @result{} (a b c a b c)
+@end group
+@end example
+@noindent
+The function @code{delq} offers a way to perform this operation
+destructively. See @ref{Sets And Lists}.
+@end defun
+
@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}.
+primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
+operations because they change existing list structure.
@cindex CL note---@code{rplaca} vrs @code{setcar}
@quotation
@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 point to @var{object}. It returns the
+@sc{car} slot of @var{cons} to refer to @var{object}. It returns the
value @var{object}. For example:
@example
@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 point to @var{object}. It returns the
+@sc{cdr} slot of @var{cons} to refer to @var{object}. It returns the
value @var{object}.
@end defun
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.
+to them as arguments, relinking their cons cells to form a new list that
+is the returned value.
-@ifinfo
+@ifnottex
See @code{delq}, in @ref{Sets And Lists}, for another function
that modifies cons cells.
-@end ifinfo
+@end ifnottex
@iftex
The function @code{delq} in the following section is another example
of destructive list manipulation.
This function destructively removes all elements @code{eq} to
@var{object} from @var{list}. The letter @samp{q} in @code{delq} says
that it uses @code{eq} to compare @var{object} against the elements of
-the list, like @code{memq}.
+the list, like @code{memq} and @code{remq}.
@end defun
When @code{delq} deletes elements from the front of the list, it does so
@end example
@end defun
-@defun delete object list
-This function destructively removes all elements @code{equal} to
-@var{object} from @var{list}. It is to @code{delq} as @code{member} is
-to @code{memq}: it uses @code{equal} to compare elements with
-@var{object}, like @code{member}; when it finds an element that matches,
-it removes the element just as @code{delq} would. For example:
+@defun delete object sequence
+If @code{sequence} is a list, this function destructively removes all
+elements @code{equal} to @var{object} from @var{sequence}. For lists,
+@code{delete} is to @code{delq} as @code{member} is to @code{memq}: it
+uses @code{equal} to compare elements with @var{object}, like
+@code{member}; when it finds an element that matches, it removes the
+element just as @code{delq} would.
+
+If @code{sequence} is a vector or string, @code{delete} returns a copy
+of @code{sequence} with all elements @code{equal} to @code{object}
+removed.
+
+For example:
@example
@group
(delete '(2) '((2) (1) (2)))
@result{} ((1))
@end group
+@group
+(delete '(2) [(2) (1) (2)])
+ @result{} [(1)]
+@end group
+@end example
+@end defun
+
+@defun remove object sequence
+This function is the non-destructive counterpart of @code{delete}. If
+returns a copy of @code{sequence}, a list, vector, or string, with
+elements @code{equal} to @code{object} removed. For example:
+
+@example
+@group
+(remove '(2) '((2) (1) (2)))
+ @result{} ((1))
+@end group
+@group
+(remove '(2) [(2) (1) (2)])
+ @result{} [(1)]
+@end group
@end example
@end defun
@quotation
-@b{Common Lisp note:} The functions @code{member} and @code{delete} in
-GNU Emacs Lisp are derived from Maclisp, not Common Lisp. The Common
-Lisp versions do not use @code{equal} to compare elements.
+@b{Common Lisp note:} The functions @code{member}, @code{delete} and
+@code{remove} in GNU Emacs Lisp are derived from Maclisp, not Common
+Lisp. The Common Lisp versions do not use @code{equal} to compare
+elements.
@end quotation
See also the function @code{add-to-list}, in @ref{Setting Variables},
@end smallexample
@end defun
+@defun assoc-default key alist test default
+This function searches @var{alist} for a match for @var{key}. For each
+element of @var{alist}, it compares the element (if it is an atom) or
+the element's @sc{car} (if it is a cons) against @var{key}, by calling
+@var{test} with two arguments: the element or its @sc{car}, and
+@var{key}. The arguments are passed in that order so that you can get
+useful results using @code{string-match} with an alist that contains
+regular expressions (@pxref{Regexp Search}). If @var{test} is omitted
+or @code{nil}, @code{equal} is used for comparison.
+
+If an alist element matches @var{key} by this criterion,
+then @code{assoc-default} returns a value based on this element.
+If the element is a cons, then the value is the element's @sc{cdr}.
+Otherwise, the return value is @var{default}.
+
+If no alist element matches @var{key}, @code{assoc-default} returns
+@code{nil}.
+@end defun
+
@defun copy-alist alist
@cindex copying alists
This function returns a two-level deep copy of @var{alist}: it creates a
@end smallexample
@end defun
+@defun assoc-delete-all key alist
+@tindex assoc-delete-all
+This function deletes from @var{alist} all the elements whose @sc{car}
+is @var{key}. It returns the modified alist.
+@example
+(assoc-delete-all 'foo
+ '((foo 1) (bar 2) (foo 3) (lose 4)))
+ @result{} ((bar 2) (lose 4))
+@end example
+@end defun