@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2002, 2003,
-@c 2004, 2005 Free Software Foundation, Inc.
+@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2001,
+@c 2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
@c See the file elisp.texi for copying conditions.
@setfilename ../info/lists
@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
@chapter Lists
-@cindex list
+@cindex lists
@cindex element (of list)
A @dfn{list} represents a sequence of zero or more elements (which may
* List-related Predicates:: Is this object a list? Comparing two lists.
* List Elements:: Extracting the pieces of a list.
* Building Lists:: Creating list structure.
+* List Variables:: Modifying lists stored in variables.
* Modifying Lists:: Storing new pieces into an existing list.
* Sets And Lists:: A list can represent a finite mathematical set.
* Association Lists:: A list can represent a finite relation or mapping.
@node Cons Cells
@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
@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
@end example
@end defun
-@need 2000
@node List Elements
@section Accessing Elements of Lists
@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.
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}))}.
-
-@example
-(setq l '(a b))
- @result{} (a b)
-(push 'c l)
- @result{} (c a b)
-l
- @result{} (c a b)
-@end example
-@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}
@end example
@end defun
+@node List Variables
+@section Modifying List Variables
+
+ These functions, and one macro, provide convenient ways
+to modify a list which is stored in a variable.
+
+@defmac push newelt listname
+This macro provides an alternative way to write
+@code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
+
+@example
+(setq l '(a b))
+ @result{} (a b)
+(push 'c l)
+ @result{} (c a b)
+l
+ @result{} (c a b)
+@end example
+@end defmac
+
+ Two functions modify lists that are the values of variables.
+
+@defun add-to-list symbol element &optional append compare-fn
+This function sets the variable @var{symbol} by consing @var{element}
+onto the old value, if @var{element} is not already a member of that
+value. It returns the resulting list, whether updated or not. The
+value of @var{symbol} had better be a list already before the call.
+@code{add-to-list} uses @var{compare-fn} to compare @var{element}
+against existing list members; if @var{compare-fn} is @code{nil}, it
+uses @code{equal}.
+
+Normally, if @var{element} is added, it is added to the front of
+@var{symbol}, but if the optional argument @var{append} is
+non-@code{nil}, it is added at the end.
+
+The argument @var{symbol} is not implicitly quoted; @code{add-to-list}
+is an ordinary function, like @code{set} and unlike @code{setq}. Quote
+the argument yourself if that is what you want.
+@end defun
+
+Here's a scenario showing how to use @code{add-to-list}:
+
+@example
+(setq foo '(a b))
+ @result{} (a b)
+
+(add-to-list 'foo 'c) ;; @r{Add @code{c}.}
+ @result{} (c a b)
+
+(add-to-list 'foo 'b) ;; @r{No effect.}
+ @result{} (c a b)
+
+foo ;; @r{@code{foo} was changed.}
+ @result{} (c a b)
+@end example
+
+ An equivalent expression for @code{(add-to-list '@var{var}
+@var{value})} is this:
+
+@example
+(or (member @var{value} @var{var})
+ (setq @var{var} (cons @var{value} @var{var})))
+@end example
+
+@defun add-to-ordered-list symbol element &optional order
+This function sets the variable @var{symbol} by inserting
+@var{element} into the old value, which must be a list, at the
+position specified by @var{order}. If @var{element} is already a
+member of the list, its position in the list is adjusted according
+to @var{order}. Membership is tested using @code{eq}.
+This function returns the resulting list, whether updated or not.
+
+The @var{order} is typically a number (integer or float), and the
+elements of the list are sorted in non-decreasing numerical order.
+
+@var{order} may also be omitted or @code{nil}. Then the numeric order
+of @var{element} stays unchanged if it already has one; otherwise,
+@var{element} has no numeric order. Elements without a numeric list
+order are placed at the end of the list, in no particular order.
+
+Any other value for @var{order} removes the numeric order of @var{element}
+if it already has one; otherwise, it is equivalent to @code{nil}.
+
+The argument @var{symbol} is not implicitly quoted;
+@code{add-to-ordered-list} is an ordinary function, like @code{set}
+and unlike @code{setq}. Quote the argument yourself if that is what
+you want.
+
+The ordering information is stored in a hash table on @var{symbol}'s
+@code{list-order} property.
+@end defun
+
+Here's a scenario showing how to use @code{add-to-ordered-list}:
+
+@example
+(setq foo '())
+ @result{} nil
+
+(add-to-ordered-list 'foo 'a 1) ;; @r{Add @code{a}.}
+ @result{} (a)
+
+(add-to-ordered-list 'foo 'c 3) ;; @r{Add @code{c}.}
+ @result{} (a c)
+
+(add-to-ordered-list 'foo 'b 2) ;; @r{Add @code{b}.}
+ @result{} (a b c)
+
+(add-to-ordered-list 'foo 'b 4) ;; @r{Move @code{b}.}
+ @result{} (a c b)
+
+(add-to-ordered-list 'foo 'd) ;; @r{Append @code{d}.}
+ @result{} (a c b d)
+
+(add-to-ordered-list 'foo 'e) ;; @r{Add @code{e}}.
+ @result{} (a c b e d)
+
+foo ;; @r{@code{foo} was changed.}
+ @result{} (a c b e d)
+@end example
+
@node Modifying Lists
@section Modifying Existing List Structure
@cindex destructive list operations
@end group
@end example
-@need 4000
Here is the result in box notation:
-@example
+@smallexample
@group
--------------------
| |
| | | | | | | | |
-------------- -------------- --------------
@end group
-@end example
+@end smallexample
@noindent
The second cons cell, which previously held the element @code{b}, still
@end defun
@defun delq object list
-@cindex deletion of elements
+@cindex deleting list elements
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
(delq '(4) sample-list)
@result{} (a c (4))
@end group
+
+If you want to delete elements that are @code{equal} to a given value,
+use @code{delete} (see below).
@end example
@defun remq object 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
+
+@defun memql object list
+The function @code{memql} tests to see whether @var{object} is a member
+of @var{list}, comparing members with @var{object} using @code{eql},
+so floating point elements are compared by value.
+If @var{object} is a member, @code{memql} returns a list starting with
+its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
+
+Compare this with @code{memq}:
+
+@example
+@group
+(memql 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are @code{eql}.}
+ @result{} (1.2 1.3)
+@end group
+@group
+(memq 1.2 '(1.1 1.2 1.3)) ; @r{@code{1.2} and @code{1.2} are not @code{eq}.}
+ @result{} nil
+@end group
+@end example
@end defun
The following three functions are like @code{memq}, @code{delq} and
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.
+@code{member}; when it finds an element that matches, it cuts the
+element out 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}
@example
@group
-(delete '(2) '((2) (1) (2)))
+(setq l '((2) (1) (2)))
+(delete '(2) l)
@result{} ((1))
+l
+ @result{} ((2) (1))
+;; @r{If you want to change @code{l} reliably,}
+;; @r{write @code{(setq l (delete elt l))}.}
+@end group
+@group
+(setq l '((2) (1) (2)))
+(delete '(1) l)
+ @result{} ((2) (2))
+l
+ @result{} ((2) (2))
+;; @r{In this case, it makes no difference whether you set @code{l},}
+;; @r{but you should do so for the sake of the other case.}
@end group
@group
(delete '(2) [(2) (1) (2)])
@end defun
@defun remove object sequence
-This function is the non-destructive counterpart of @code{delete}. If
+This function is the non-destructive counterpart of @code{delete}. It
returns a copy of @code{sequence}, a list, vector, or string, with
elements @code{equal} to @code{object} removed. For example:
@code{delete-dups} keeps the first one.
@end defun
- 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.
+ See also the function @code{add-to-list}, in @ref{List Variables},
+for a way to an element to a list stored in a variable and used as a
+set.
@node Association Lists
@section Association Lists
@end group
@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
+ Both the values and the keys in an alist may be any Lisp objects.
+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:
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
+ The same alist shown above could be regarded as having the
associated value in the @sc{cdr} of the element; the value associated
with @code{rose} would be the list @code{(red)}.
@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
+@var{alist}, comparing @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:
@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.
+this as ``reverse @code{assoc},'' finding the key for a given value.
@end defun
@defun assq key alist
@code{rassq} is like @code{assq} 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{assq}'', finding the key for a given value.
+this as ``reverse @code{assq},'' finding the key for a given value.
For example:
@result{} nil
@end smallexample
-Note that @code{rassq} cannot search for a value stored in the @sc{car}
+@code{rassq} cannot search for a value stored in the @sc{car}
of the @sc{cdr} of an element:
@smallexample
@end defun
@defun assq-delete-all key alist
-@tindex assq-delete-all
This function deletes from @var{alist} all the elements whose @sc{car}
is @code{eq} to @var{key}, much as if you used @code{delq} to delete
each such element one by one. It returns the shortened alist, and