Build Fix -- compatibility issue with newer autoconf

[sxemacs] / info / lispref / lists.texi

@c -*-texinfo-*-
@c This is part of the SXEmacs Lisp Reference Manual.
@c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
@c Copyright (C) 2005, 2006 Sebastian Freundt <hroptatyr@sxemacs.org>
@c See the file lispref.texi for copying conditions.
@setfilename ../../info/lists.info

@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
@chapter Lists
@cindex list
@cindex element (of list)

  A @dfn{list} represents a sequence of zero or more elements (which may
be any Lisp objects).  The important difference between lists and
vectors is that two or more lists can share part of their structure; in
addition, you can insert or delete elements in a list without copying
the whole list.

@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.
* 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.
* Property Lists::          A different way to represent a finite mapping.
* Skip Lists::              Very efficient dictionary data type.
* Weak Lists::              A list with special garbage-collection behavior.
* DL-Lists::                A doubly-linked list implementation.
* Bloom Filters::           A special set type with anonymous membership.
@end menu


@node Cons Cells, Lists as Boxes, Lists, Lists
@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}).

  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, List-related Predicates, Cons Cells, Lists
@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 ``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.

  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.


@node List-related Predicates, List Elements, Lists as Boxes, Lists
@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.)

@defun consp object
This function returns @code{t} if @var{object} is a cons cell, @code{nil}
otherwise.  @code{nil} is not a cons cell, although it @emph{is} a list.
@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
that is both.

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

@defun listp object
This function returns @code{t} if @var{object} is a cons cell or
@code{nil}.  Otherwise, it returns @code{nil}.

@example
@group
(listp '(1))
     @result{} t
@end group
@group
(listp '())
     @result{} t
@end group
@end example
@end defun

@defun nlistp object
This function is the opposite of @code{listp}: it returns @code{t} if
@var{object} is not a list.  Otherwise, it returns @code{nil}.

@example
(listp @var{object}) @equiv{} (not (nlistp @var{object}))
@end example
@end defun

@defun null object
This function returns @code{t} if @var{object} is @code{nil}, and
returns @code{nil} otherwise.  This function is identical to @code{not},
but as a matter of clarity we use @code{null} when @var{object} is
considered a list and @code{not} when it is considered a truth value
(see @code{not} in @ref{Combining Conditions}).

@example
@group
(null '(1))
     @result{} nil
@end group
@group
(null '())
     @result{} t
@end group
@end example
@end defun

@need 2000


@node List Elements, Building Lists, List-related Predicates, Lists
@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
cons cell @var{cons-cell}.  Expressed another way, this function
returns the @sc{car} of @var{cons-cell}.

As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
is defined to return @code{nil}; therefore, any list is a valid argument
for @code{car}.  An error is signaled if the argument is not a cons cell
or @code{nil}.

@example
@group
(car '(a b c))
     @result{} a
@end group
@group
(car '())
     @result{} nil
@end group
@end example
@end defun

@defun cdr cons-cell
This function returns the value pointed to by the second pointer of
the cons cell @var{cons-cell}.  Expressed another way, this function
returns the @sc{cdr} of @var{cons-cell}.

As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
is defined to return @code{nil}; therefore, any list is a valid argument
for @code{cdr}.  An error is signaled if the argument is not a cons cell
or @code{nil}.

@example
@group
(cdr '(a b c))
     @result{} (b c)
@end group
@group
(cdr '())
     @result{} nil
@end group
@end example
@end defun

@defun car-safe object
This function lets you take the @sc{car} of a cons cell while avoiding
errors for other data types.  It returns the @sc{car} of @var{object} if
@var{object} is a cons cell, @code{nil} otherwise.  This is in contrast
to @code{car}, which signals an error if @var{object} is not a list.

@example
@group
(car-safe @var{object})
@equiv{}
(let ((x @var{object}))
  (if (consp x)
      (car x)
    nil))
@end group
@end example
@end defun

@defun cdr-safe object
This function lets you take the @sc{cdr} of a cons cell while
avoiding errors for other data types.  It returns the @sc{cdr} of
@var{object} if @var{object} is a cons cell, @code{nil} otherwise.
This is in contrast to @code{cdr}, which signals an error if
@var{object} is not a list.

@example
@group
(cdr-safe @var{object})
@equiv{}
(let ((x @var{object}))
  (if (consp x)
      (cdr x)
    nil))
@end group
@end example
@end defun

@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
element number zero.  If the length of @var{list} is @var{n} or less,
the value is @code{nil}.

If @var{n} is negative, @code{nth} returns the first element of
@var{list}.

@example
@group
(nth 2 '(1 2 3 4))
     @result{} 3
@end group
@group
(nth 10 '(1 2 3 4))
     @result{} nil
@end group
@group
(nth -3 '(1 2 3 4))
     @result{} 1

(nth n x) @equiv{} (car (nthcdr n x))
@end group
@end example
@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
what follows.

If @var{n} is zero or negative, @code{nthcdr} returns all of
@var{list}.  If the length of @var{list} is @var{n} or less,
@code{nthcdr} returns @code{nil}.

@example
@group
(nthcdr 1 '(1 2 3 4))
     @result{} (2 3 4)
@end group
@group
(nthcdr 10 '(1 2 3 4))
     @result{} nil
@end group
@group
(nthcdr -3 '(1 2 3 4))
     @result{} (1 2 3 4)
@end group
@end example
@end defun

Many convenience functions are provided to make it easier for you to
access particular elements in a nested list.  All of these can be
rewritten in terms of the functions just described.

@defun caar cons-cell
@defunx cadr cons-cell
@defunx cdar cons-cell
@defunx cddr cons-cell
@defunx caaar cons-cell
@defunx caadr cons-cell
@defunx cadar cons-cell
@defunx caddr cons-cell
@defunx cdaar cons-cell
@defunx cdadr cons-cell
@defunx cddar cons-cell
@defunx cdddr cons-cell
@defunx caaaar cons-cell
@defunx caaadr cons-cell
@defunx caadar cons-cell
@defunx caaddr cons-cell
@defunx cadaar cons-cell
@defunx cadadr cons-cell
@defunx caddar cons-cell
@defunx cadddr cons-cell
@defunx cdaaar cons-cell
@defunx cdaadr cons-cell
@defunx cdadar cons-cell
@defunx cdaddr cons-cell
@defunx cddaar cons-cell
@defunx cddadr cons-cell
@defunx cdddar cons-cell
@defunx cddddr cons-cell
Each of these functions is equivalent to one or more applications of
@code{car} and/or @code{cdr}.  For example,

@example
(cadr x)
@end example

is equivalent to

@example
(car (cdr x))
@end example

and

@example
(cdaddr x)
@end example

is equivalent to

@example
(cdr (car (cdr (cdr x))))
@end example

That is to say, read the a's and d's from right to left and apply
a @code{car} or @code{cdr} for each a or d found, respectively.
@end defun

@defun first list
This is equivalent to @code{(nth 0 @var{list})}, i.e. the first element
of @var{list}. (Note that this is also equivalent to @code{car}.)
@end defun

@defun second list
This is equivalent to @code{(nth 1 @var{list})}, i.e. the second element
of @var{list}.
@end defun

@defun third list
@defunx fourth list
@defunx fifth list
@defunx sixth list
@defunx seventh list
@defunx eighth list
@defunx ninth list
@defunx tenth list
These are equivalent to @code{(nth 2 @var{list})} through
@code{(nth 9 @var{list})} respectively, i.e. the third through tenth
elements of @var{list}.
@end defun


@node Building Lists, Modifying Lists, List Elements, Lists
@section Building Cons Cells and Lists
@cindex cons cells
@cindex building lists

  Many functions build lists, as lists reside at the very heart of Lisp.
@code{cons} is the fundamental list-building function; however, it is
interesting to note that @code{list} is used more times in the source
code for SXEmacs than @code{cons}.

@defun cons object1 object2
This function is the fundamental function used to build 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.

@example
@group
(cons 1 '(2))
     @result{} (1 2)
@end group
@group
(cons 1 '())
     @result{} (1)
@end group
@group
(cons 1 2)
     @result{} (1 . 2)
@end group
@end example

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

@example
(setq list (cons newelt list))
@end example

Note that there is no conflict between the variable named @code{list}
used in this example and the function named @code{list} described below;
any symbol can serve both purposes.
@end defun

@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}
are given, the empty list is returned.

@example
@group
(list 1 2 3 4 5)
     @result{} (1 2 3 4 5)
@end group
@group
(list 1 2 '(3 4 5) 'foo)
     @result{} (1 2 (3 4 5) foo)
@end group
@group
(list)
     @result{} nil
@end group
@end example
@end defun

@defun make-list length object
This function creates a list of length @var{length}, in which all the
elements have the identical value @var{object}.  Compare
@code{make-list} with @code{make-string} (@pxref{Creating Strings}).

@example
@group
(make-list 3 'pigs)
     @result{} (pigs pigs pigs)
@end group
@group
(make-list 0 'pigs)
     @result{} nil
@end group
@end example
@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)
(setq more-trees (append '(maple birch) trees))
     @result{} (maple birch pine oak)
@end group

@group
trees
     @result{} (pine oak)
more-trees
     @result{} (maple birch pine oak)
@end group
@group
(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
|                           |
|     ___ ___      ___ ___   -> ___ ___      ___ ___
 --> |___|___|--> |___|___|--> |___|___|--> |___|___|--> nil
       |            |            |            |
       |            |            |            |
        --> maple    -->birch     --> pine     --> oak
@end group
@end smallexample

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.

@example
@group
trees
     @result{} (pine oak)
@end group
@group
(setq wood (append trees ()))
     @result{} (pine oak)
@end group
@group
wood
     @result{} (pine oak)
@end group
@group
(eq wood trees)
     @result{} nil
@end group
@end example

@noindent
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:

@example
@group
(apply 'append '((a b c) nil (x y z) nil))
     @result{} (a b c x y z)
@end group
@end example

If no @var{sequences} are given, @code{nil} is returned:

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

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
@emph{not} altered.

@example
@group
(setq x '(1 2 3 4))
     @result{} (1 2 3 4)
@end group
@group
(reverse x)
     @result{} (4 3 2 1)
x
     @result{} (1 2 3 4)
@end group
@end example
@end defun


@node Modifying Lists, Sets And Lists, Building Lists, Lists
@section Modifying Existing List Structure

  You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
primitives @code{setcar} and @code{setcdr}.

@cindex CL note---@code{rplaca} vrs @code{setcar}
@quotation
@findex rplaca
@findex rplacd
@b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
@code{rplacd} to alter list structure; they change structure the same
way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
return the cons cell while @code{setcar} and @code{setcdr} return the
new @sc{car} or @sc{cdr}.
@end quotation

@menu
* Setcar::          Replacing an element in a list.
* Setcdr::          Replacing part of the list backbone.
                      This can be used to remove or add elements.
* Rearrangement::   Reordering the elements in a list; combining lists.
@end menu


@node Setcar, Setcdr, Modifying Lists, Modifying Lists
@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-cell object
This function stores @var{object} as the new @sc{car} of @var{cons-cell},
replacing its previous @sc{car}.  It returns the value @var{object}.
For example:

@example
@group
(setq x '(1 2))
     @result{} (1 2)
@end group
@group
(setcar x 4)
     @result{} 4
@end group
@group
x
     @result{} (4 2)
@end group
@end example
@end defun

  When a cons cell is part of the shared structure of several lists,
storing a new @sc{car} into the cons changes one element of each of
these lists.  Here is an example:

@example
@group
;; @r{Create two lists that are partly shared.}
(setq x1 '(a b c))
     @result{} (a b c)
(setq x2 (cons 'z (cdr x1)))
     @result{} (z b c)
@end group

@group
;; @r{Replace the @sc{car} of a shared link.}
(setcar (cdr x1) 'foo)
     @result{} foo
x1                           ; @r{Both lists are changed.}
     @result{} (a foo c)
x2
     @result{} (z foo c)
@end group

@group
;; @r{Replace the @sc{car} of a link that is not shared.}
(setcar x1 'baz)
     @result{} baz
x1                           ; @r{Only one list is changed.}
     @result{} (baz foo c)
x2
     @result{} (z foo c)
@end group
@end example

  Here is a graphical depiction of the shared structure of the two lists
in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
changes them both:

@example
@group
        ___ ___        ___ ___      ___ ___
x1---> |___|___|----> |___|___|--> |___|___|--> nil
         |        -->   |            |
         |       |      |            |
          --> a  |       --> b        --> c
                 |
       ___ ___   |
x2--> |___|___|--
        |
        |
         --> z
@end group
@end example

  Here is an alternative form of box diagram, showing the same relationship:

@example
@group
x1:
 --------------       --------------       --------------
| car   | cdr  |     | car   | cdr  |     | car   | cdr  |
|   a   |   o------->|   b   |   o------->|   c   |  nil |
|       |      |  -->|       |      |     |       |      |
 --------------  |    --------------       --------------
                 |
x2:              |
 --------------  |
| car   | cdr  | |
|   z   |   o----
|       |      |
 --------------
@end group
@end example


@node Setcdr, Rearrangement, Setcar, Modifying Lists
@subsection Altering the CDR of a List

  The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:

@defun setcdr cons-cell object
This function stores @var{object} as the new @sc{cdr} of @var{cons-cell},
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
unchanged, because it resides in the @sc{car} of the list, and is not
reached via the @sc{cdr}.

@example
@group
(setq x '(1 2 3))
     @result{} (1 2 3)
@end group
@group
(setcdr x '(4))
     @result{} (4)
@end group
@group
x
     @result{} (1 4)
@end group
@end example

  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:

@example
@group
(setq x1 '(a b c))
     @result{} (a b c)
(setcdr x1 (cdr (cdr x1)))
     @result{} (c)
x1
     @result{} (a c)
@end group
@end example

@need 4000
  Here is the result in box notation:

@example
@group
                   --------------------
                  |                    |
 --------------   |   --------------   |    --------------
| car   | cdr  |  |  | car   | cdr  |   -->| car   | cdr  |
|   a   |   o-----   |   b   |   o-------->|   c   |  nil |
|       |      |     |       |      |      |       |      |
 --------------       --------------        --------------
@end group
@end example

@noindent
The second cons cell, which previously held the element @code{b}, still
exists and its @sc{car} is still @code{b}, but it no longer forms part
of this list.

  It is equally easy to insert a new element by changing @sc{cdr}s:

@example
@group
(setq x1 '(a b c))
     @result{} (a b c)
(setcdr x1 (cons 'd (cdr x1)))
     @result{} (d b c)
x1
     @result{} (a d b c)
@end group
@end example

  Here is this result in box notation:

@smallexample
@group
 --------------        -------------       -------------
| car  | cdr   |      | car  | cdr  |     | car  | cdr  |
|   a  |   o   |   -->|   b  |   o------->|   c  |  nil |
|      |   |   |  |   |      |      |     |      |      |
 --------- | --   |    -------------       -------------
           |      |
     -----         --------
    |                      |
    |    ---------------   |
    |   | car   | cdr   |  |
     -->|   d   |   o------
        |       |       |
         ---------------
@end group
@end smallexample


@node Rearrangement,  , Setcdr, Modifying Lists
@subsection Functions that Rearrange Lists
@cindex rearrangement of lists
@cindex modification of lists

  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
@emph{not} copied.  Instead, the last @sc{cdr} of each of the
@var{lists} is changed to refer to the following list.  The last of the
@var{lists} is not altered.  For example:

@example
@group
(setq x '(1 2 3))
     @result{} (1 2 3)
@end group
@group
(nconc x '(4 5))
     @result{} (1 2 3 4 5)
@end group
@group
x
     @result{} (1 2 3 4 5)
@end group
@end example

   Since the last argument of @code{nconc} is not itself modified, it is
reasonable to use a constant list, such as @code{'(4 5)}, as in the
above example.  For the same reason, the last argument need not be a
list:

@example
@group
(setq x '(1 2 3))
     @result{} (1 2 3)
@end group
@group
(nconc x 'z)
     @result{} (1 2 3 . z)
@end group
@group
x
     @result{} (1 2 3 . z)
@end group
@end example

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:

@smallexample
@group
(defun add-foo (x)            ; @r{We want this function to add}
  (nconc '(foo) x))           ;   @r{@code{foo} to the front of its arg.}
@end group

@group
(symbol-function 'add-foo)
     @result{} (lambda (x) (nconc (quote (foo)) x))
@end group

@group
(setq xx (add-foo '(1 2)))    ; @r{It seems to work.}
     @result{} (foo 1 2)
@end group
@group
(setq xy (add-foo '(3 4)))    ; @r{What happened?}
     @result{} (foo 1 2 3 4)
@end group
@group
(eq xx xy)
     @result{} t
@end group

@group
(symbol-function 'add-foo)
     @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
@end group
@end smallexample
@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
(setq x '(1 2 3 4))
     @result{} (1 2 3 4)
@end group
@group
x
     @result{} (1 2 3 4)
(nreverse x)
     @result{} (4 3 2 1)
@end group
@group
;; @r{The cell that was first is now last.}
x
     @result{} (1)
@end group
@end example

  To avoid confusion, we usually store the result of @code{nreverse}
back in the same variable which held the original list:

@example
(setq x (nreverse x))
@end example

  Here is the @code{nreverse} of our favorite example, @code{(a b c)},
presented graphically:

@smallexample
@group
@r{Original list head:}                       @r{Reversed list:}
 -------------        -------------        ------------
| car  | cdr  |      | car  | cdr  |      | car | cdr  |
|   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
|      |      |   |  |      |   |  |   |  |     |   |  |
 -------------    |   --------- | -    |   -------- | -
                  |             |      |            |
                   -------------        ------------
@end group
@end smallexample
@end defun

@defun sort list predicate
@cindex stable sort
@cindex sorting lists
This function sorts @var{list} stably, though destructively, and
returns the sorted list.  It compares elements using @var{predicate}.  A
stable sort is one in which elements with equal sort keys maintain their
relative order before and after the sort.  Stability is important when
successive sorts are used to order elements according to different
criteria.

The argument @var{predicate} must be a function that accepts two
arguments.  It is called with two elements of @var{list}.  To get an
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 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
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:

@example
@group
(setq nums '(1 3 2 6 5 4 0))
     @result{} (1 3 2 6 5 4 0)
@end group
@group
(sort nums '<)
     @result{} (0 1 2 3 4 5 6)
@end group
@group
nums
     @result{} (1 2 3 4 5 6)
@end group
@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:

@example
(setq nums (sort nums '<))
@end 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, Association Lists, Modifying Lists, Lists
@section Using Lists as Sets
@cindex lists as sets
@cindex sets

  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
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}
@quotation
@b{Common Lisp note:} Common Lisp has functions @code{union} (which
avoids duplicate elements) and @code{intersection} for set operations,
but SXEmacs Lisp does not have them.  You can write them in Lisp if
you wish.
@end quotation

@defun memq object list
@cindex membership in a list
This function tests to see whether @var{object} is a member of
@var{list}.  If it is, @code{memq} returns a list starting with the
first occurrence of @var{object}.  Otherwise, it returns @code{nil}.
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
@end example
@end defun

@defun delq object list
@cindex deletion of 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
the list, like @code{memq}.
@end defun

When @code{delq} deletes elements from the front of the list, it does so
simply by advancing down the list and returning a sublist that starts
after those elements:

@example
@group
(delq 'a '(a b c)) @equiv{} (cdr '(a b c))
@end group
@end example

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 b (4))
@end group
@group
sample-list
     @result{} (a b (4))
@end group
@end example

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
result of @code{delq} and use that.  Most often we store the result back
into the variable that held the original list:

@example
(setq flowers (delq 'rose flowers))
@end example

In the following example, the @code{(4)} that @code{delq} attempts to match
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
Emacs 19.

@defun member object list
The function @code{member} tests to see whether @var{object} is a member
of @var{list}, comparing members with @var{object} using @code{equal}.
If @var{object} is a member, @code{member} returns a list starting with
its first occurrence in @var{list}.  Otherwise, it returns @code{nil}.

Compare this with @code{memq}:

@example
@group
(member '(2) '((1) (2)))  ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
     @result{} ((2))
@end group
@group
(memq '(2) '((1) (2)))    ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
     @result{} nil
@end group
@group
;; @r{Two strings with the same contents are @code{equal}.}
(member "foo" '("foo" "bar"))
     @result{} ("foo" "bar")
@end group
@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:

@example
@group
(delete '(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
SXEmacs 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},
for another way to add an element to a list stored in a variable.


@node Association Lists, Property Lists, Sets And Lists, Lists
@section Association Lists
@cindex association list
@cindex alist

  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
@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
the alist associations are the items.}

  Here is an example of an alist.  The key @code{pine} is associated with
the value @code{cones}; the key @code{oak} is associated with
@code{acorns}; and the key @code{maple} is associated with @code{seeds}.

@example
@group
'((pine . cones)
  (oak . acorns)
  (maple . seeds))
@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
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:

@example
((a . 1) ("b" 2 3))
@end example

  Sometimes it is better to design an alist to store the associated
value in the @sc{car} of the @sc{cdr} of the element.  Here is an
example:

@example
'((rose red) (lily white) (buttercup yellow))
@end example

@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
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
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
associated value in the @sc{cdr} of the element; the value associated
with @code{rose} would be the list @code{(red)}.

  Association lists are often used to record information that you might
otherwise keep on a stack, since new associations may be added easily to
the front of the list.  When searching an association list for an
association with a given key, the first one found is returned, if there
is more than one.

  In SXEmacs Lisp, it is @emph{not} an error if an element of an
association list is not a cons cell.  The alist search functions simply
ignore such elements.  Many other versions of Lisp signal errors in such
cases.

  Note that property lists are similar to association lists in several
respects.  A property list behaves like an association list in which
each key can occur only once.  @xref{Property Lists}, for a comparison
of property lists and association lists.

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

@smallexample
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     @result{} ((pine . cones) (oak . acorns) (maple . seeds))
(assoc 'oak trees)
     @result{} (oak . acorns)
(cdr (assoc 'oak trees))
     @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")
        (5 "White Pine")))

(cdr (assoc 3 needles-per-cluster))
     @result{} ("Pitch Pine")
(cdr (assoc 2 needles-per-cluster))
     @result{} ("Austrian Pine" "Red Pine")
@end smallexample
@end defun

@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
This function is like @code{assoc} in that it returns the first
association for @var{key} in @var{alist}, but it makes the comparison
using @code{eq} instead of @code{equal}.  @code{assq} returns @code{nil}
if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
This function is used more often than @code{assoc}, since @code{eq} is
faster than @code{equal} and most alists use symbols as keys.
@xref{Equality Predicates}.

@smallexample
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     @result{} ((pine . cones) (oak . acorns) (maple . seeds))
(assq 'pine trees)
     @result{} (pine . cones)
@end smallexample

On the other hand, @code{assq} is not usually useful in alists where the
keys may not be symbols:

@smallexample
(setq leaves
      '(("simple leaves" . oak)
        ("compound leaves" . horsechestnut)))

(assq "simple leaves" leaves)
     @result{} nil
(assoc "simple leaves" leaves)
     @result{} ("simple leaves" . oak)
@end smallexample
@end defun

@defun rassq 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{eq} to @var{value}.

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

For example:

@smallexample
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))

(rassq 'acorns trees)
     @result{} (oak . acorns)
(rassq 'spores trees)
     @result{} nil
@end smallexample

Note that @code{rassq} cannot search for a value stored in the @sc{car}
of the @sc{cdr} of an element:

@smallexample
(setq colors '((rose red) (lily white) (buttercup yellow)))

(rassq 'white colors)
     @result{} nil
@end smallexample

In this case, the @sc{cdr} of the association @code{(lily white)} is not
the symbol @code{white}, but rather the list @code{(white)}.  This
becomes clearer if the association is written in dotted pair notation:

@smallexample
(lily white) @equiv{} (lily . (white))
@end smallexample
@end defun

@defun remassoc key alist
This function deletes by side effect any associations with key @var{key}
in @var{alist}---i.e. it removes any elements from @var{alist} whose
@code{car} is @code{equal} to @var{key}.  The modified @var{alist} is
returned.

If the first member of @var{alist} has a @code{car} that is @code{equal}
to @var{key}, there is no way to remove it by side effect; therefore,
write @code{(setq foo (remassoc key foo))} to be sure of changing the
value of @code{foo}.
@end defun

@defun remassq key alist
This function deletes by side effect any associations with key @var{key}
in @var{alist}---i.e. it removes any elements from @var{alist} whose
@code{car} is @code{eq} to @var{key}.  The modified @var{alist} is
returned.

This function is exactly like @code{remassoc}, but comparisons between
@var{key} and keys in @var{alist} are done using @code{eq} instead of
@code{equal}.
@end defun

@defun remrassoc value alist
This function deletes by side effect any associations with value @var{value}
in @var{alist}---i.e. it removes any elements from @var{alist} whose
@code{cdr} is @code{equal} to @var{value}.  The modified @var{alist} is
returned.

If the first member of @var{alist} has a @code{car} that is @code{equal}
to @var{value}, there is no way to remove it by side effect; therefore,
write @code{(setq foo (remassoc value foo))} to be sure of changing the
value of @code{foo}.

@code{remrassoc} is like @code{remassoc} 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{remassoc}'', removing an association
based on its value instead of its key.
@end defun

@defun remrassq value alist
This function deletes by side effect any associations with value @var{value}
in @var{alist}---i.e. it removes any elements from @var{alist} whose
@code{cdr} is @code{eq} to @var{value}.  The modified @var{alist} is
returned.

This function is exactly like @code{remrassoc}, but comparisons between
@var{value} and values in @var{alist} are done using @code{eq} instead of
@code{equal}.
@end defun

@defun copy-alist alist
@cindex copying alists
This function returns a two-level deep copy of @var{alist}: it creates a
new copy of each association, so that you can alter the associations of
the new alist without changing the old one.

@smallexample
@group
(setq needles-per-cluster
      '((2 . ("Austrian Pine" "Red Pine"))
        (3 . ("Pitch Pine"))
@end group
        (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")
@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


@node Property Lists, Skip Lists, Association Lists, Lists
@section Property Lists
@cindex property list
@cindex plist

A @dfn{property list} (or @dfn{plist}) is another way of representing a
mapping from keys to values.  Instead of the list consisting of conses
of a key and a value, the keys and values alternate as successive
entries in the list.  Thus, the association list

@example
((a . 1) (b . 2) (c . 3))
@end example

has the equivalent property list form

@example
(a 1 b 2 c 3)
@end example

Property lists are used to represent the properties associated with
various sorts of objects, such as symbols, strings, frames, etc.
The convention is that property lists can be modified in-place,
while association lists generally are not.

Plists come in two varieties: @dfn{normal} plists, whose keys are
compared with @code{eq}, and @dfn{lax} plists, whose keys are compared
with @code{equal},

@defun valid-plist-p plist
Given a plist, this function returns non-@code{nil} if its format is
correct.  If it returns @code{nil}, @code{check-valid-plist} will signal
an error when given the plist; that means it's a malformed or circular
plist or has non-symbols as keywords.
@end defun

@defun check-valid-plist plist
Given a plist, this function signals an error if there is anything wrong
with it.  This means that it's a malformed or circular plist.
@end defun

@menu
* Working With Normal Plists::       Functions for normal plists.
* Working With Lax Plists::          Functions for lax plists.
* Converting Plists To/From Alists:: Alist to plist and vice-versa.
@end menu


@node Working With Normal Plists, Working With Lax Plists, Property Lists, Property Lists
@subsection Working With Normal Plists

@defun plist-get plist property &optional default
This function extracts a value from a property list.  The function
returns the value corresponding to the given @var{property}, or
@var{default} if @var{property} is not one of the properties on the list.
@end defun

@defun plist-put plist property value
This function changes the value in @var{plist} of @var{property} to
@var{value}.  If @var{property} is already a property on the list, its value is
set to @var{value}, otherwise the new @var{property} @var{value} pair is added.
The new plist is returned; use @code{(setq x (plist-put x property value))} to
be sure to use the new value.  The @var{plist} is modified by side
effects.
@end defun

@defun plist-remprop plist property
This function removes from @var{plist} the property @var{property} and its
value.  The new plist is returned; use @code{(setq x (plist-remprop x
property))} to be sure to use the new value.  The @var{plist} is
modified by side effects.
@end defun

@defun plist-member plist property
This function returns @code{t} if @var{property} has a value specified in
@var{plist}.
@end defun

In the following functions, if optional arg @var{nil-means-not-present}
is non-@code{nil}, then a property with a @code{nil} value is ignored or
removed.  This feature is a virus that has infected old Lisp
implementations (and thus E-Lisp, due to @sc{rms}'s enamorment with old
Lisps), but should not be used except for backward compatibility.

@defun plists-eq a b &optional nil-means-not-present
This function returns non-@code{nil} if property lists A and B are
@code{eq} (i.e. their values are @code{eq}).
@end defun

@defun plists-equal a b &optional nil-means-not-present
This function returns non-@code{nil} if property lists A and B are
@code{equal} (i.e. their values are @code{equal}; their keys are
still compared using @code{eq}).
@end defun

@defun canonicalize-plist plist &optional nil-means-not-present
This function destructively removes any duplicate entries from a plist.
In such cases, the first entry applies.

The new plist is returned.  If @var{nil-means-not-present} is given, the
return value may not be @code{eq} to the passed-in value, so make sure
to @code{setq} the value back into where it came from.
@end defun


@node Working With Lax Plists, Converting Plists To/From Alists, Working With Normal Plists, Property Lists
@subsection Working With Lax Plists

Recall that a @dfn{lax plist} is a property list whose keys are compared
using @code{equal} instead of @code{eq}.

@defun lax-plist-get lax-plist property &optional default
This function extracts a value from a lax property list.  The function
returns the value corresponding to the given @var{property}, or
@var{default} if @var{property} is not one of the properties on the list.
@end defun

@defun lax-plist-put lax-plist property value
This function changes the value in @var{lax-plist} of @var{property} to @var{value}.
@end defun

@defun lax-plist-remprop lax-plist property
This function removes from @var{lax-plist} the property @var{property} and
its value.  The new plist is returned; use @code{(setq x
(lax-plist-remprop x property))} to be sure to use the new value.  The
@var{lax-plist} is modified by side effects.
@end defun

@defun lax-plist-member lax-plist property
This function returns @code{t} if @var{property} has a value specified in
@var{lax-plist}.
@end defun

In the following functions, if optional arg @var{nil-means-not-present}
is non-@code{nil}, then a property with a @code{nil} value is ignored or
removed.  This feature is a virus that has infected old Lisp
implementations (and thus E-Lisp, due to @sc{rms}'s enamorment with old
Lisps), but should not be used except for backward compatibility.

@defun lax-plists-eq a b &optional nil-means-not-present
This function returns non-@code{nil} if lax property lists A and B are
@code{eq} (i.e. their values are @code{eq}; their keys are still
compared using @code{equal}).
@end defun

@defun lax-plists-equal a b &optional nil-means-not-present
This function returns non-@code{nil} if lax property lists A and B are
@code{equal} (i.e. their values are @code{equal}).
@end defun

@defun canonicalize-lax-plist lax-plist &optional nil-means-not-present
This function destructively removes any duplicate entries from a lax
plist.  In such cases, the first entry applies.

The new plist is returned.  If @var{nil-means-not-present} is given, the
return value may not be @code{eq} to the passed-in value, so make sure
to @code{setq} the value back into where it came from.
@end defun


@node Converting Plists To/From Alists,  , Working With Lax Plists, Property Lists
@subsection Converting Plists To/From Alists

@defun alist-to-plist alist
This function converts association list @var{alist} into the equivalent
property-list form.  The plist is returned.  This converts from

@example
((a . 1) (b . 2) (c . 3))
@end example

into

@example
(a 1 b 2 c 3)
@end example

The original alist is not modified.
@end defun

@defun plist-to-alist plist
This function converts property list @var{plist} into the equivalent
association-list form.  The alist is returned.  This converts from

@example
(a 1 b 2 c 3)
@end example

into

@example
((a . 1) (b . 2) (c . 3))
@end example

The original plist is not modified.
@end defun

The following two functions are equivalent to the preceding two except
that they destructively modify their arguments, using cons cells from
the original list to form the new list rather than allocating new
cons cells.

@defun destructive-alist-to-plist alist
This function destructively converts association list @var{alist} into
the equivalent property-list form.  The plist is returned.
@end defun

@defun destructive-plist-to-alist plist
This function destructively converts property list @var{plist} into the
equivalent association-list form.  The alist is returned.
@end defun


@node Skip Lists, Weak Lists, Property Lists, Lists
@section Skip Lists
@cindex skip list

Like association lists or property lists, a skip list is another
dictionary data type.  That is skip lists can be used to represent a
finite key-value mapping.  See @xref{Association Lists}, and
@xref{Property Lists}.

However, alists and plists are very inefficient at almost any
operation for large key spaces.  For instance, looking up the value of
a given key is accomplished by linear probing.  This implies that
searching for a key not in the key space is a worst case, the list has
to be traversed in its entirety as it contains no superior structure
or indicators which help to identify keys not belonging to the key
space.

On the other hand, given an alist or plist this lack of structure
induces a class of equivalent alists or plists with respect to the
storage representation.  This would make it possible to add new
elements in constant time by just prepending them to the front of the
list.

Anyway, without manual intervention SXEmacs' association and property
lists @strong{cannot} add elements in constant time.  Instead they try
to avoid duplicate keys and thence crawl the entire list to make sure
the key to be added is not already there.


@defun make-skiplist
Return a new empty skiplist object.
@end defun

@defun skiplistp object
Return non-@code{nil} if @var{object} is a skiplist, @code{nil}
otherwise.
@end defun

@defun skiplist-empty-p skiplist
Return non-@code{nil} if @var{skiplist} is empty, @code{nil}
otherwise.
@end defun

@defun put-skiplist skiplist key value
Add @var{key} to the @var{skiplist} and assign @var{value}.
Hereby, the skiplist object is modified by side-effect.
@end defun

@defun get-skiplist skiplist key &optional default
Return the value of @var{key} in @var{skiplist}.
If @var{key} is not an element, return @code{nil} instead or --
if specified -- @var{default}.
@end defun

@defun remove-skiplist skiplist key
Remove the element specified by @var{key} from @var{skiplist}.
If @var{key} is not an element, this is a no-op.
@end defun

@defun skiplist-owns-p skiplist key
Return non-@code{nil} if @var{key} is associated with a value in
@var{skiplist}, @code{nil} otherwise.
@end defun

@defun skiplist-size skiplist
Return the size of @var{skiplist}, that is the number of elements.
@end defun

@defun copy-skiplist skiplist
Return a copy of skiplist @var{skiplist}.
The elements of @var{skiplist} are not copied; they are shared
with the original.
@end defun

@defun skiplist-to-alist skiplist
Return the ordinary association list induced by @var{skiplist}.
@end defun

@defun skiplist-to-plist skiplist
Return the ordinary property list induced by @var{skiplist}.
@end defun

@defun alist-to-skiplist alist
Return a skiplist from @var{alist} with equal key space and image.
@end defun

@defun plist-to-skiplist plist
Return a skiplist from @var{plist} with equal key space and image.
@end defun

@defun skiplist-union &rest skiplists
Return the union skiplist of @var{skiplists},
that is a skiplist containing all key-value-pairs which are in at
least one skiplist of @var{skiplists}.

Note: Key-value-pairs with equal keys and distinct values are
processed from left to right, that is the final union for such pairs
contains the value of the rightmost skiplist in @var{skiplists}.
@end defun

@defun skiplist-intersection &rest skiplists
Return the intersection skiplist of @var{skiplists},
that is a skiplist containing all key-value-pairs which are in all
skiplists of @var{skiplists}.

Note: Key-value-pairs with equal keys and distinct values are
processed from right to left, that is the final intersection for such
pairs contains the value of the leftmost skiplist in @var{skiplists}.
@end defun

@defun map-skiplist function skiplist
Map @var{function} over entries in @var{skiplist}, calling it with two
args, each key and value in @var{skiplist}.

@var{function} may not modify @var{skiplist}, with the one exception
that @var{function} may remove or reput the entry currently being
processed by @var{function}.
@end defun



@node Weak Lists, DL-Lists, Skip Lists, Lists
@section Weak Lists
@cindex weak list

A @dfn{weak list} is a special sort of list whose members are not counted
as references for the purpose of garbage collection.  This means that,
for any object in the list, if there are no references to the object
anywhere outside of the list (or other weak list or weak hash table),
that object will disappear the next time a garbage collection happens.
Weak lists can be useful for keeping track of things such as unobtrusive
lists of another function's buffers or markers.  When that function is
done with the elements, they will automatically disappear from the list.

Weak lists are used internally, for example, to manage the list holding
the children of an extent---an extent that is unused but has a parent
will still be reclaimed, and will automatically be removed from its
parent's list of children.

Weak lists are similar to weak hash tables (@pxref{Weak Hash Tables}).

@defun weak-list-p object
This function returns non-@code{nil} if @var{object} is a weak list.
@end defun

Weak lists come in one of four types:

@table @code
@item simple
Objects in the list disappear if not referenced outside of the list.

@item assoc
Objects in the list disappear if they are conses and either the car or
the cdr of the cons is not referenced outside of the list.

@item key-assoc
Objects in the list disappear if they are conses and the car is not
referenced outside of the list.

@item value-assoc
Objects in the list disappear if they are conses and the cdr is not
referenced outside of the list.
@end table

@defun make-weak-list &optional type
This function creates a new weak list of type @var{type}.  @var{type} is
a symbol (one of @code{simple}, @code{assoc}, @code{key-assoc}, or
@code{value-assoc}, as described above) and defaults to @code{simple}.
@end defun

@defun weak-list-type weak
This function returns the type of the given weak-list object.
@end defun

@defun weak-list-list weak
This function returns the list contained in a weak-list object.
@end defun

@defun set-weak-list-list weak new-list
This function changes the list contained in a weak-list object.
@end defun


@node DL-Lists, Bloom Filters, Weak Lists, Lists
@section Doubly-Linked Lists
@cindex dl-list
@cindex doubly-linked list

  A doubly-linked list is a mere extension of the ordinary linked list.
While the latter one has an entry pointer to the first element of the
list (obtainable via @code{car}) and for each element a pointer to the
next element (obtainable via @code{cdr}), the doubly-linked list
(dl-list for short) has both, an entry pointer to the first element and
an entry pointer to the last element.  These are obtainable via
@code{dllist-car} and @code{dllist-rac}, respectively.  Moreover, all
elements of the dl-list point to the next and the previous element.

  This well-known structure supports both appending and prepending
elements in the same time complexity class.

@defun dllist &rest initial-elements
Return a doubly-linked list.

Optionally passed arguments are filled into the resulting dllist.
@end defun

@defun dllistp object
Return non-@code{nil} if @var{object} is a dllist, @code{nil}
otherwise.
@end defun

@defun dllist-empty-p dllist
Return non-@code{nil} if @var{dllist} is empty, @code{nil} otherwise.
@end defun

@defun dllist-size dllist
Return the size of @var{dllist}, that is the number of elements.
@end defun


@defun dllist-car dllist
Return the front element of @var{dllist}.
@end defun

@defun dllist-rac dllist
Return the back element of @var{dllist}.
@end defun

@noindent
Note: All of the following modifier functions work by side-effect.

@defun dllist-prepend dllist element
Add @var{element} to the front of @var{dllist}.
@end defun

@defun dllist-append dllist element
Add @var{element} to the back of @var{dllist}.
@end defun

@defun dllist-pop-car dllist
Remove the front element of @var{dllist} and return it.
@end defun

@defun dllist-pop-rac dllist
Remove the back element of @var{dllist} and return it.
@end defun

In box notation a dllist looks like
@smallexample
@group
car         _______     _______
|          |       |   |       |    --> nil
|     _____|_     _v___|_     _v___|_
 --> |_______|   |_______|   |_______| <--
       | | ^       | | ^       | |        |
nil <--  | |_______| | |_______| |        |
         v           v           v        rac
       data1       data2       data3
@end group
@end smallexample



@noindent
Let us look at some examples.

@example
@group
(setq d (dllist))
  @result{} (dllist)
(dllistp d)
  @result{} t
@end group

@group
(dllist-append d 2)
  @result{} (dllist 2)
(dllist-append d 4)
  @result{} (dllist 2 4)
(dllist-append d 6)
  @result{} (dllist 2 4 6)
@end group

@group
(dllist-car d)
  @result{} 2
(dllist-rac d)
  @result{} 6
@end group

@group
(dllist-prepend d (dllist-pop-rac d))
  @result{} (dllist 6 2 4)
(dllist-append d (dllist-pop-car d))
  @result{} (dllist 2 4 6)
(dllist-size d)
  @result{} 3
@end group
@end example

@noindent
Of course, dl-lists can be converted to ordinary lisp lists.

@defun dllist-to-list dllist
Return the ordinary list induced by @var{dllist}, that is start with
the first element in @var{dllist} and traverse through the back.
@end defun

@defun dllist-to-list-reversed dllist
Return the ordinary list induced by @var{dllist} in reverse order,
that is start with the last element in @var{dllist} and traverse
through the front.
@end defun

@example
@group
(dllist-to-list d)
  @result{} (2 4 6)
(dllist-to-list-reversed d)
  @result{} (6 4 2)
@end group
@end example


@node Bloom Filters,  , DL-Lists, Lists
@section Bloom Filters
@cindex Bloom filters

  The concept of a Bloom filter was introduces by Burton H. Bloom in 1970.
It is a constant space complexity, probabilistic data structure that is
used to do so-called membership decisions on anonymous sets.  That is,
you can easily decide whether a given element is a member of a certain
set, whereas you cannot select elements from it (or even traverse
through all elements).  Moreover, like hash-tables the time complexity
of Bloom filters for adding and removing elements, as well as
membership-decision is in O(1) -- it is in O(@var{k}) indeed where
@var{k} is the degree of the Bloom filter.

  Probabilistic, however, means that false positives are possible, but
false negatives are not.  The probability of false positives grows
subexponentially with the number of added elements.

  Another interesting property of Bloom filters of equal order and
degree is the ability to perform set union and intersection operations
within O(1) space and time complexity!

  SXEmacs' Bloom filters have their own lisp-type, but they do not have
a special input syntax.

@defun make-bloom &optional order degree
Return an empty bloom-filter.

Optional argument @var{order} (a positive integer) specifies the
``length'' of the internal filter vector, defaults to 256.

Optional argument @var{degree} (a positive integer) specifies the
number of hash slices, defaults to 8.
@end defun

  For reasons of convenience, we also provide a constructor for a
complete Bloom filter.  That is a bloom filter which owns any possible
element.

@defun make-bloom-universe &optional order degree
Return a complete bloom-filter.

Optional argument @var{order} (a positive integer) specifies the
``length'' of the internal filter vector, defaults to 256.

Optional argument @var{degree} (a positive integer) specifies the
number of hash slices, defaults to 8.
@end defun


@defun bloomp object
Return non-@code{nil} if @var{object} is a bloom filter,
@code{nil} otherwise.
@end defun

  There are two further auxiliary functions to determine the bloom
filter parameters:

@defun bloom-order bloom
Return the order of the bloom-filter @var{bloom}.
@end defun

@defun bloom-degree bloom
Return the degree of the bloom-filter @var{bloom}.
@end defun


  Adding/removing elements to/from a bloom filter always works by
side-effect.

@defun bloom-add bloom element
Add @var{element} to the bloom-filter @var{bloom}.
@end defun

@defun bloom-remove bloom element
Remove @var{element} from the bloom-filter @var{bloom}.
@end defun

@noindent
The membership decision is done with @code{bloom-owns-p}.

@defun bloom-owns-p bloom element
Return non-@code{nil} if @var{element} is in the bloom-filter
@var{bloom}.
@end defun


@example
(setq bl (make-bloom))
  @result{} #<bloom-filter :order 256 :degree 8 :size 0>
(bloomp bl)
  @result{} t
@end example

@noindent
Now we want to add three integers and test some memberships.

@example
@group
(bloom-add bl 12)
  @result{} 12
(bloom-add bl 21)
  @result{} 21
(bloom-add bl 0)
  @result{} 0
@end group

@group
(bloom-owns-p bl 12)
  @result{} t
(bloom-owns-p bl 21)
  @result{} t
(bloom-owns-p bl 0)
  @result{} t
(bloom-owns-p bl 13)
  @result{} nil
(bloom-owns-p bl 17)
  @result{} nil
@end group
@end example

@noindent
Now let us remove some elements

@example
@group
(bloom-remove bl 12)
  @result{} 12
(bloom-remove bl 0)
  @result{} 12
@end group

@group
(bloom-owns-p bl 12)
  @result{} nil
(bloom-owns-p bl 21)
  @result{} t
(bloom-owns-p bl 0)
  @result{} nil
@end group
@end example

  Of course, Bloom filters work with any lisp type (not just integers).
Internally, they use an object's hash value and scatter it over a
fixed-length array.

@example
@group
(bloom-owns-p bl "horse")
  @result{} nil
(bloom-add bl "horse")
  @result{} "horse"
(bloom-owns-p bl "horse")
  @result{} t
(bloom-owns-p bl "snake")
  @result{} nil
@end group
@end example


  As remarked above, union and intersection of Bloom-filters of equal
order and degree is possible in constant time regardless of the size.

@defun bloom-union &rest blooms
Return the union Bloom filter of all arguments.
@end defun

@defun bloom-intersection &rest blooms
Return the intersection Bloom filter of all arguments.
@end defun

@example
@group
(setq bl1 (make-bloom))
  @result{} #<bloom-filter :order 256 :degree 8 :size 0>
(bloom-add bl1 2)
  @result{} 2
(bloom-add bl1 4)
  @result{} 4
(bloom-add bl1 'foobar)
  @result{} foobar
@end group

@group
(setq bl2 (make-bloom))
  @result{} #<bloom-filter :order 256 :degree 8 :size 0>
(bloom-add bl2 "horse")
  @result{} "horse"
(bloom-add bl2 "snail")
  @result{} "snail"
(bloom-add bl2 'foobar)
  @result{} foobar
@end group

@group
(setq blu (bloom-union bl1 bl2))
  @result{} #<bloom-filter :order 256 :degree 8 :size 6>
(bloom-owns-p blu 2)
  @result{} t
(bloom-owns-p blu 4)
  @result{} t
(bloom-owns-p blu "horse")
  @result{} t
(bloom-owns-p blu "snail")
  @result{} t
(bloom-owns-p blu 'foobar)
  @result{} t
@end group

@group
(setq bli (bloom-intersection bl1 bl2))
  @result{} #<bloom-filter :order 256 :degree 8 :size 0>
(bloom-owns-p bli 2)
  @result{} nil
(bloom-owns-p bli 4)
  @result{} nil
(bloom-owns-p bli "horse")
  @result{} nil
(bloom-owns-p bli "snail")
  @result{} nil
(bloom-owns-p bli 'foobar)
  @result{} t
@end group
@end example


  Now we want to illustrate the extreme performance gain over lists, and
compare to the performance of hash-tables.  Therefore, we use a setup
routine which fills a data container with 10000 distinct elements.  Then
we do 50000 membership tests. Let's start with ordinary lisp lists.  For
each of these both tests we measure the time.

@example
@group
(defun test-element ()
  "Return a random test element."
  (incf cnt))
  @result{} test-element
@end group
@end example

@example
@group
(setq tlist (list))
  @result{} nil
(setq cnt 0)
  @result{} 0
(let ((start (current-btime)))
  (dotimes (i 10000)
    (setq tlist (cons (test-element) tlist)))
  (- (current-btime) start))
  @result{} 140733
@end group

@group
;; 50000 membership tests on tlist @dots{} take a coffee break
(setq cnt 0)
  @result{} 0
(let ((start (current-btime)))
  (dotimes (i 50000)
    (member (test-element) tlist))
  (- (current-btime) start))
  @result{} 154817323
@end group
@end example

@noindent
Let's consider hash-tables:
@example
@group
(setq thash (make-hash-table))
  @result{} #<hash-table size 0/29 0x1619>
(setq cnt 0)
  @result{} 0
(let ((start (current-btime)))
  (dotimes (i 10000)
    (puthash (test-element) 'some-value thash))
  (- (current-btime) start))
  @result{} 173210
@end group

@group
;; 50000 membership tests on thash
(setq cnt 0)
  @result{} 0
(let ((start (current-btime)))
  (dotimes (i 50000)
    (gethash (test-element) thash))
  (- (current-btime) start))
  @result{} 723030
@end group
@end example

@noindent
Let's finish our considerations with Bloom filters:
@example
@group
(setq tbfil (make-bloom))
  @result{} #<bloom-filter :order 256 :degree 8 :size 0>
(setq cnt 0)
  @result{} 0
(let ((start (current-btime)))
  (dotimes (i 10000)
    (bloom-add tbfil (test-element)))
  (- (current-btime) start))
  @result{} 128565
@end group

@group
;; 50000 membership tests on tbfil
(setq cnt 0)
  @result{} 0
(let ((start (current-btime)))
  (dotimes (i 50000)
    (bloom-owns-p tbfil (test-element)))
  (- (current-btime) start))
  @result{} 757945
@end group
@end example

  Evaluating all these results, we can state that hash-tables and
Bloom-filters provide equal performance.  For extremely large sets,
Bloom-filters may profit from the absence of resizing the underlying
array.

@example
@group
;; 400000 insertions into a bloom-filter
(setq tbfil (make-bloom))
  @result{} #<bloom-filter :order 256 :degree 8 :size 0>
(setq cnt 0)
  @result{} 0
(let ((start (current-btime)))
  (dotimes (i 400000)
    (bloom-add tbfil (test-element)))
  (- (current-btime) start))
  @result{} 5464420
@end group

@group
;; 400000 insertions into a hash-table
(setq thash (make-hash-table))
  @result{} #<hash-table size 0/29 0x1066>
(setq cnt 0)
  @result{} 0
(let ((start (current-btime)))
  (dotimes (i 400000)
    (puthash (test-element) 'some-value thash))
  (- (current-btime) start))
  @result{} 6392474
@end group
@end example

  Furthermore, Bloom filters are able to track how often equal elements
have been inserted, for hash-tables the value field may be used to
implement something similar.

  However, bloom filters tend to report more and more false positives
the more elements you add.  False negatives are @strong{never}
possible.  That means with a sufficiently small bloom filter and a
sufficiently large set of elements it is just a matter of probability
when this filter will turn into a universe.

@example
(setq b4 (make-bloom 256 64))
  @result{} #<bloom-filter :order 256 :degree 64 :size 0>

;; now add 800000 numbers to it
(dotimes (i 800000)
  (bloom-add b4 i))
  @result{} nil

;; now check this
(bloom-owns-p b4 'a-symbol-I-never-added)
  @result{} t
(bloom-owns-p b4 "a string I never added")
  @result{} t
(bloom-owns-p b4 [a vector I never added])
  @result{} t
@end example

@noindent
We see that @code{b4} has turned into a quasi-universe.  There might
be objects which are not yet in @code{b4}, but the probability to find
one is extremely small.

  Given a bloom filter of degree @var{d} and size @var{s}, and given
the bloom filter already contains @var{n} elements, the exact
probability to get a false positive (an element which has not been
added, but @code{bloom-owns-p} reports so) is:

@iftex
@tex
$$
\left(1 - \left(1 - {1\over s}\right)^{dn}\right)^d
$$
@end tex
@end iftex
@ifinfo
(1 - (1 - 1/s)^(d*n))^d
@end ifinfo

@noindent
So for our example the probability is veeery close to one, to be
precise, it is:

@smallexample
0.9999...99993386493554255105254275560...
  ^^^^^^^^^^^
  87027 times
@end smallexample

@c @c @c lists.texi ends here