@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999
+@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999,
+@c 2003, 2004, 2005
@c Free Software Foundation, Inc.
@c See the file elisp.texi for copying conditions.
@setfilename ../info/lists
@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.
level of cons cells, the @sc{car} and @sc{cdr} slots have the same
characteristics.
+@cindex true list
+ Since @code{nil} is the conventional value to put in the @sc{cdr} of
+the last cons cell in the list, we call that case a @dfn{true list}.
+
+ In Lisp, we consider the symbol @code{nil} 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}). Therefore, the @sc{cdr} of a true list is always a
+true list.
+
+@cindex dotted list
+@cindex circular list
+ If the @sc{cdr} of a list's last cons cell is some other value,
+neither @code{nil} nor another cons cell, we call the structure a
+@dfn{dotted list}, since its printed representation would use
+@samp{.}. There is one other possibility: some cons cell's @sc{cdr}
+could point to one of the previous cons cells in the list. We call
+that structure a @dfn{circular list}.
+
+ For some purposes, it does not matter whether a list is true,
+circular or dotted. If the program doesn't look far enough down the
+list to see the @sc{cdr} of the final cons cell, it won't care.
+However, some functions that operate on lists demand true lists and
+signal errors if given a dotted list. Most functions that try to find
+the end of a list enter infinite loops if given a circular list.
+
@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}).
-
The @sc{cdr} of any nonempty list @var{l} is a list containing all the
elements of @var{l} except the first.
-@node Lists as Boxes
-@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:
-
-@example
-@group
- --------------- ---------------
-| car | cdr | | car | cdr |
-| tulip | o---------->| lily | nil |
-| | | | | |
- --------------- ---------------
-@end group
-@end example
-
- Each pair of boxes represents a cons cell. Each box ``refers to'',
-``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
- --- --- --- ---
- | |
- | |
- --> tulip --> lily
-@end group
-@end example
-
- Here is a more complex illustration, showing the three-element list,
-@code{((pine needles) oak maple)}, the first element of which is a
-two-element list:
-
-@example
-@group
- --- --- --- --- --- ---
- | | |--> | | |--> | | |--> nil
- --- --- --- --- --- ---
- | | |
- | | |
- | --> oak --> maple
- |
- | --- --- --- ---
- --> | | |--> | | |--> nil
- --- --- --- ---
- | |
- | |
- --> pine --> needles
-@end group
-@end example
-
- The same list represented in the first box notation looks like this:
-
-@example
-@group
- -------------- -------------- --------------
-| car | cdr | | car | cdr | | car | cdr |
-| o | o------->| oak | o------->| maple | nil |
-| | | | | | | | | |
- -- | --------- -------------- --------------
- |
- |
- | -------------- ----------------
- | | car | cdr | | car | cdr |
- ------>| pine | o------->| needles | nil |
- | | | | | |
- -------------- ----------------
-@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.
+lists, and for ``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
-cons cell or is a list, or whether it is the distinguished object
-@code{nil}. (Many of these predicates can be defined in terms of the
-others, but they are used so often that it is worth having all of them.)
+ The following predicates test whether a Lisp object is an atom,
+whether it is a cons cell or is a list, or whether it is the
+distinguished object @code{nil}. (Many of these predicates 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}
@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.
+and taking it off the list, all at once.
It operates on the list which is stored in the symbol @var{listname}.
It removes this element from the list by setting @var{listname}
@end defmac
@defun nth n list
+@anchor{Definition of nth}
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,
@end defun
@defun safe-length list
-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.
+@anchor{Definition of safe-length}
+This function returns the length of @var{list}, with no risk of either
+an error or an infinite loop. It generally returns the number of
+distinct cons cells in the list. However, for circular lists,
+the value is just an upper bound; it is often too large.
+
+If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
+returns 0.
@end defun
The most common way to compute the length of a list, when you are not
code for Emacs than @code{cons}.
@defun cons object1 object2
-This function is the fundamental function used to build new list
+This function is the most basic function for building 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.
+@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
@group
@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.
@example
(setq l '(a b))
@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
+dotted list since its final @sc{cdr} is not @code{nil} as required
in a true list.
In Emacs 20 and before, the @code{append} function also allowed
@end defun
@defun copy-tree tree &optional vecp
-This function returns a copy the tree @code{tree}. If @var{tree} is a
+This function returns a copy of the tree @code{tree}. If @var{tree} is a
cons cell, this makes a new cons cell with the same @sc{car} and
@sc{cdr}, then recursively copies the @sc{car} and @sc{cdr} in the
same way.
incrementing by @var{separation}, and ending at or just before
@var{to}. @var{separation} can be positive or negative and defaults
to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
-the one element list @code{(from)} is returned. If @var{separation}
-is 0 and @var{to} is neither @code{nil} nor numerically equal to
-@var{from}, an error is signaled.
+the value is the one-element list @code{(@var{from})}. If @var{to} is
+less than @var{from} with a positive @var{separation}, or greater than
+@var{from} with a negative @var{separation}, the value is @code{nil}
+because those arguments specify an empty sequence.
+
+If @var{separation} is 0 and @var{to} is neither @code{nil} nor
+numerically equal to @var{from}, @code{number-sequence} signals an
+error, since those arguments specify an infinite sequence.
All arguments can be integers or floating point numbers. However,
floating point arguments can be tricky, because floating point
arithmetic is inexact. For instance, depending on the machine, it may
quite well happen that @code{(number-sequence 0.4 0.6 0.2)} returns
-the one element list @code{(0.4)}, whereas
+the one element list @code{(0.4)}, whereas
@code{(number-sequence 0.4 0.8 0.2)} returns a list with three
elements. The @var{n}th element of the list is computed by the exact
formula @code{(+ @var{from} (* @var{n} @var{separation}))}. Thus, if
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). Other useful
+long as you don't mind having duplicate elements). You can remove
+@code{equal} duplicates using @code{delete-dups}. Other useful
functions for sets include @code{memq} and @code{delq}, and their
@code{equal} versions, @code{member} and @code{delete}.
representation: upper-case and lower-case letters are treated as
equal, and unibyte strings are converted to multibyte prior to
comparison.
+@end defun
+
+@defun delete-dups list
+This function destructively removes all @code{equal} duplicates from
+@var{list}, stores the result in @var{list} and returns it. Of
+several @code{equal} occurrences of an element in @var{list},
+@code{delete-dups} keeps the first one.
@end defun
See also the function @code{add-to-list}, in @ref{Setting Variables},