@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
+@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998 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
@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.''
+@dfn{cons cells}. A cons cell is a data object that represents an
+ordered pair. It holds, or ``refers 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
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
@end example
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.
+``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
+that the @sc{cdr} of the first cons cell is the second cons cell.
The same list can be illustrated in a different sort of box notation
like this:
@example
@group
- ___ ___ ___ ___
- |___|___|--> |___|___|--> nil
+ --- --- --- ---
+ | | |--> | | |--> nil
+ --- --- --- ---
| |
| |
--> tulip --> lily
@example
@group
- ___ ___ ___ ___ ___ ___
- |___|___|--> |___|___|--> |___|___|--> nil
+ --- --- --- --- --- ---
+ | | |--> | | |--> | | |--> nil
+ --- --- --- --- --- ---
| | |
| | |
| --> oak --> maple
|
- | ___ ___ ___ ___
- --> |___|___|--> |___|___|--> nil
+ | --- --- --- ---
+ --> | | |--> | | |--> nil
+ --- --- --- ---
| |
| |
--> pine --> needles
@end group
@end example
- @xref{List Type}, for the read and print syntax of lists, and for more
-``box and arrow'' illustrations of lists.
+ @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
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.
+that is both.
@example
(atom @var{object}) @equiv{} (not (consp @var{object}))
@end example
@end defun
-@need 1000
+@need 2000
@node List Elements
@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
+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}.
(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 removes the first @var{n} links of @var{list} and returns
+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
@end example
@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.
+
+If @var{list} is not really a list, @code{safe-length} returns 0. If
+@var{list} is circular, it returns a finite value which is at least the
+number of distinct elements.
+@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
+@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
+
@node Building Lists
@comment node-name, next, previous, up
@section Building Cons Cells and Lists
@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.
+@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.
+
+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:
+ Here is an example of using @code{append}:
@example
@group
@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:
+ 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
+| --- --- --- --- -> --- --- --- ---
+ --> | | |--> | | |--> | | |--> | | |--> nil
+ --- --- --- --- --- --- --- ---
| | | |
| | | |
--> maple -->birch --> pine --> oak
@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
@result{} (pine oak)
@end group
@group
-(setq wood (append trees ()))
+(setq wood (append trees nil))
@result{} (pine oak)
@end group
@group
This once was the usual 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:
+ 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
@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
-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:
+ Here are some examples where the final argument is not a list:
@example
-@group
-(setq trees '(pine oak))
- @result{} (pine oak)
-@end group
-@group
-(char-to-string 54)
- @result{} "6"
-@end group
-@group
-(setq longer-list (append trees 6 '(spruce)))
- @result{} (pine oak 54 spruce)
-@end group
-@group
-(setq x-list (append trees 6 6))
- @result{} (pine oak 54 . 6)
-@end group
+(append '(x y) 'z)
+ @result{} (x y . z)
+(append '(x y) [z])
+ @result{} (x y . [z])
@end example
-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{number-to-string} (@pxref{String Conversion}).
-@end defun
+@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
@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
@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.
+ 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:
+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
@example
@group
- ___ ___ ___ ___ ___ ___
-x1---> |___|___|----> |___|___|--> |___|___|--> nil
+ --- --- --- --- --- ---
+x1---> | | |----> | | |--> | | |--> nil
+ --- --- --- --- --- ---
| --> | |
| | | |
--> a | --> b --> c
|
- ___ ___ |
-x2--> |___|___|--
+ --- --- |
+x2--> | | |--
+ --- ---
|
|
--> z
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}.
+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
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:
+the @sc{cdr} of the first cons cell:
@example
@group
@end group
@end example
+@need 4000
Here is the result in box notation:
@example
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
+ 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
@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:
@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.
+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:
@result{} (4 3 2 1)
@end group
@group
-;; @r{The cell that was first is now last.}
+;; @r{The cons cell that was first is now last.}
x
@result{} (1)
@end group
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 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
@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:
+@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 '<))
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
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{set}
+@cindex CL note---lack @code{union}, @code{intersection}
@quotation
@b{Common Lisp note:} Common Lisp has functions @code{union} (which
avoids duplicate elements) and @code{intersection} for set operations,
@example
@group
-(memq 2 '(1 2 3 2 1))
- @result{} (2 3 2 1)
+(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}.}
@example
@group
-(setq sample-list '(1 2 3 (4)))
- @result{} (1 2 3 (4))
+(setq sample-list '(a b c (4)))
+ @result{} (a b c (4))
@end group
@group
-(delq 1 sample-list)
- @result{} (2 3 (4))
+(delq 'a sample-list)
+ @result{} (b c (4))
@end group
@group
sample-list
- @result{} (1 2 3 (4))
+ @result{} (a b c (4))
@end group
@group
-(delq 2 sample-list)
- @result{} (1 3 (4))
+(delq 'c sample-list)
+ @result{} (a b (4))
@end group
@group
sample-list
- @result{} (1 3 (4))
+ @result{} (a b (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
+Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
+splice out the third 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
@example
@group
(delq '(4) sample-list)
- @result{} (1 3 (4))
+ @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
-Emacs 19.
+@code{equal} rather than @code{eq} to compare elements. @xref{Equality
+Predicates}.
@defun member object list
The function @code{member} tests to see whether @var{object} is a member
@example
@group
(delete '(2) '((2) (1) (2)))
- @result{} '((1))
+ @result{} ((1))
@end group
@end example
@end defun
Lisp versions do not use @code{equal} to compare elements.
@end quotation
+ See also the function @code{add-to-list}, in @ref{Setting Variables},
+for another way to add an element to a list stored in a variable.
+
@node Association Lists
@section Association Lists
@cindex association list
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
+@dfn{associations}: the @sc{car} of each cons cell is the @dfn{key}, and the
@sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
is not related to the term ``key sequence''; it means a value used to
look up an item in a table. In this case, the table is the alist, and
@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
+advantage of this kind of alist 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
@result{} nil
@end smallexample
-Here is another example in which the keys and values are not symbols:
+Here is another example, in which the keys and values are not symbols:
@smallexample
(setq needles-per-cluster
(cdr (assoc 2 needles-per-cluster))
@result{} ("Austrian Pine" "Red Pine")
@end smallexample
+@end defun
+
+ The functions @code{assoc-ignore-representation} and
+@code{assoc-ignore-case} are much like @code{assoc} except using
+@code{compare-strings} to do the comparison. @xref{Text Comparison}.
+
+@defun rassoc value alist
+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{equal} to @var{value}.
+
+@code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
+each @var{alist} association instead of the @sc{car}. You can think of
+this as ``reverse @code{assoc}'', finding the key for a given value.
@end defun
@defun assq key alist
@end smallexample
@end defun
+@tindex assoc-default
+@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
@group
(setq needles-per-cluster
'((2 . ("Austrian Pine" "Red Pine"))
- (3 . "Pitch Pine")
- (5 . "White Pine")))
+ (3 . ("Pitch Pine"))
+@end group
+ (5 . ("White Pine"))))
@result{}
((2 "Austrian Pine" "Red Pine")
- (3 . "Pitch Pine")
- (5 . "White 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"))
+ (3 "Pitch Pine")
+ (5 "White Pine"))
(eq needles-per-cluster copy)
@result{} nil
(eq (car needles-per-cluster) (car copy))
@result{} nil
(cdr (car (cdr needles-per-cluster)))
- @result{} "Pitch Pine"
+ @result{} ("Pitch Pine")
+@group
(eq (cdr (car (cdr needles-per-cluster)))
(cdr (car (cdr copy))))
@result{} t
@end group
+@end smallexample
+
+ This example shows how @code{copy-alist} makes it possible to change
+the associations of one copy without affecting the other:
+
+@smallexample
+@group
+(setcdr (assq 3 copy) '("Martian Vacuum Pine"))
+(cdr (assq 3 needles-per-cluster))
+ @result{} ("Pitch Pine")
+@end group
@end smallexample
@end defun