list.tex

%Part{List, Root = "CLM.MSS"}
%%% Chapter of Common Lisp Manual.  Copyright 1984, 1988, 1989 Guy L. Steele Jr.

\clearpage\def\pagestatus{FINAL PROOF}

\ifx \rulang\Undef

\chapter{Lists}

A \emph{cons}, or dotted pair, is a compound data object having two components
called the \emph{car} and \emph{cdr}.  Each component may be any Lisp object.
A \emph{list} is a chain of conses
linked by \emph{cdr} fields; the chain is terminated by some atom
(a non-cons object).
An ordinary list is terminated by {\nil}, the empty list
(also written {\emptylist}).
A list whose \emph{cdr} chain is terminated by some non-{\nil} atom is called
a \emph{dotted list}.

The recommended predicate for testing for the end of a list is \cdf{endp}.

\section{Conses}

These are the basic operations on conses viewed as pairs rather than
as the constituents of a list.

\begin{defun}[Function]
car list

This returns the \emph{car} of \emph{list}, which must be a cons or {\emptylist};
that is, \emph{list} must satisfy the predicate \cdf{listp}.
By definition, the \emph{car} of {\emptylist} is {\emptylist}.
If the cons is regarded as the first cons of a list, then \cdf{car}
returns the first element of the list.
For example:
\begin{lisp}
(car '(a b c)) \EV\ a
\end{lisp}
See \cdf{first}.
The \emph{car} of a cons may be altered by using \cdf{rplaca} or \cdf{setf}.
\end{defun}

\begin{defun}[Function]
cdr list

This returns the \emph{cdr} of \emph{list}, which must be a cons or {\emptylist};
that is, \emph{list} must satisfy the predicate \cdf{listp}.
By definition, the \emph{cdr} of {\emptylist} is {\emptylist}.
If the cons is regarded as the first cons of a list, then \cdf{cdr}
returns the rest of the list, which is a list with all elements
but the first of the original list.
For example:
\begin{lisp}
(cdr '(a b c)) \EV\ (b c)
\end{lisp}
See \cdf{rest}.
The \emph{cdr} of a cons may be altered by using \cdf{rplacd} or \cdf{setf}.
\end{defun}

\begin{defun}[Function]
caar list \\
cadr list \\
cdar list \\
cddr list \\
caaar list \\
caadr list \\
cadar list \\
caddr list \\
cdaar list \\
cdadr list \\
cddar list \\
cdddr list \\
caaaar list \\
caaadr list \\
caadar list \\
caaddr list \\
cadaar list \\
cadadr list \\
caddar list \\
cadddr list \\
cdaaar list \\
cdaadr list \\
cdadar list \\
cdaddr list \\
cddaar list \\
cddadr list \\
cdddar list \\
cddddr list

All of the compositions of up to four \cdf{car} and \cdf{cdr} operations
are defined as separate Common Lisp functions.
The names of these functions begin with \cdf{c} and end with \cdf{r},
and in between is a sequence of \cdf{a} and \cdf{d} letters
corresponding to
the composition performed by the function. 
For example:
\begin{lisp}
(cddadr x) \textrm{is the same as} (cdr (cdr (car (cdr x))))
\end{lisp}
If the argument is regarded as a list, then \cdf{cadr} returns
the second element of the list, \cdf{caddr} the third, and \cdf{cadddr}
the fourth.  If the first element of a list is a list, then
\cdf{caar} is the first element of the sublist, \cdf{cdar} is the
rest of that sublist, and \cdf{cadar} is the second element of the sublist,
and so on.

As a matter of style, it is often preferable to define a function or
macro to access part of a complicated data structure, rather than to use
a long \cdf{car}/\cdf{cdr} string.  For example, one might define
a macro to extract the list of parameter variables from a lambda-expression:
\begin{lisp}
(defmacro lambda-vars (lambda-exp) `(cadr ,lambda-exp))
\end{lisp}
and then use \cdf{lambda-vars} for this purpose instead of \cdf{cadr}.
See also \cdf{defstruct}, which will automatically define
new record data types and access functions for instances of them.

Any of these functions may be used to specify a \emph{place} for \cdf{setf}.
\end{defun}
	
\begin{defun}[Function]
cons x y

\cdf{cons} is the primitive function to create a new \emph{cons} whose
\emph{car} is \emph{x} and whose \emph{cdr} is \emph{y}.
For example:
\begin{lisp}
(cons 'a 'b) \EV\ (a . b) \\
(cons 'a (cons 'b (cons 'c '{\emptylist}))) \EV\ (a b c) \\
(cons 'a '(b c d)) \EV\ (a b c d)
\end{lisp}
\cdf{cons} may be thought of as creating a \emph{cons}, or as adding a new element
to the front of a list.
\end{defun}

\begin{defun}[Function]
tree-equal x y &key :test :test-not

This is a predicate that is true if \emph{x} and \emph{y} are
isomorphic trees with identical leaves, that is, if \emph{x} and \emph{y}
are atoms that satisfy the test (by default \cdf{eql}),
or if they are both conses and their \emph{car}'s are \cdf{tree-equal}
and their \emph{cdr}'s are \cdf{tree-equal}.
Thus \cdf{tree-equal} recursively compares conses (but not any other objects
that have components).  See \cdf{equal}, which does recursively
compare certain other structured objects, such as strings.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\section{Lists}

The following functions perform various operations on lists.

The list is one of the original Lisp data types.  The very name ``Lisp''
is an abbreviation for ``LISt Processing.''

\goodbreak

\begin{defun}[Function]
endp object

The predicate \cdf{endp} is the recommended way to test for the end
of a list.  It is false of conses, true of {\nil}, and an error for
all other arguments.

\beforenoterule
\begin{implementation}
Implementations are encouraged to signal an
error, especially in the interpreter, for a non-list argument.
The \cdf{endp} function is defined so as to allow compiled code
to perform simply an atom check or a null check if speed is more
important than safety.
\end{implementation}
\afternoterule
\end{defun}

\begin{defun}[Function]
list-length list

\cdf{list-length} returns, as an integer, the length of \emph{list}.
\cdf{list-length} differs from \cdf{length} when the \emph{list} is
circular; \cdf{length} may fail to return, whereas \cdf{list-length}
will return {\nil}.
For example:
\begin{lisp}
(list-length '{\emptylist}) \EV\ 0 \\
(list-length '(a b c d)) \EV\ 4 \\
(list-length '(a (b c) d)) \EV\ 3 \\
(let ((x (list 'a b c))) \\
~~(rplacd (last x) x) \\
~~(list-length x)) \EV\ {\nil}
\end{lisp}
\cdf{list-length} could be implemented as follows:
\begin{lisp}
(defun list-length (x) \\
~~(do ((n 0 (+ n 2))~~~~~~~~~~~~;\textrm{Counter} \\
~~~~~~~(fast x (cddr fast))~~~~~;\textrm{Fast pointer: leaps by 2} \\
~~~~~~~(slow x (cdr slow)))~~~~~;\textrm{Slow pointer: leaps by 1} \\
~~~~~~(nil) \\
~~~~;; If fast pointer hits the end, return the count. \\
~~~~(when (endp fast) (return n)) \\
~~~~(when (endp (cdr fast)) (return (+ n 1))) \\
~~~~;; If fast pointer eventually equals slow pointer, \\
~~~~;;  then we must be stuck in a circular list. \\
~~~~;; (A deeper property is the converse: if we are \\
~~~~;;  stuck in a circular list, then eventually the \\
~~~~;;  fast pointer will equal the slow pointer. \\
~~~~;;  That fact justifies this implementation.) \\
~~~~(when (and (eq fast slow) (> n 0)) (return nil))))
\end{lisp}
See \cdf{length}, which will return the length of any sequence.
\end{defun}

\begin{defun}[Function]
nth n list

\cd{(nth \emph{n} \emph{list})} returns the \emph{n}th element of \emph{list}, where
the \emph{car} of the list is the ``zeroth'' element.
The argument \emph{n} must be a non-negative integer.
If the length of the list is not greater than \emph{n}, then the result
is {\emptylist}, that is, {\false}.
(This is consistent with the idea that the \emph{car} and \emph{cdr}
of {\emptylist} are each {\emptylist}.)
For example:
\begin{lisp}
(nth 0 '(foo bar gack)) \EV\ foo \\
(nth 1 '(foo bar gack)) \EV\ bar \\
(nth 3 '(foo bar gack)) \EV\ {\emptylist}
\end{lisp}

\cdf{nth} may be used to specify a \emph{place} to \cdf{setf};
when \cdf{nth} is used in this way, the argument \emph{n} must be less
than the length of the \emph{list}.

Note that the arguments to \cdf{nth} are reversed from the order
used by most other sequence selector functions such as \cdf{elt}.
\end{defun}


\begin{defun}[Function]
first list \\
second list \\
third list \\
fourth list \\
fifth list \\
sixth list \\
seventh list \\
eighth list \\
ninth list \\
tenth list

These functions are sometimes convenient for accessing particular
elements of a list.  \cdf{first} is the same as \cdf{car},
\cdf{second} is the same as \cdf{cadr}, \cdf{third} is the
same as \cdf{caddr}, and so on.
Note that the ordinal numbering used here is one-origin,
as opposed to the zero-origin numbering used by \cdf{nth}:
\begin{lisp}
(fifth x) \EQ\ (nth 4 x)
\end{lisp}

\cdf{setf} may be used with each of these functions to store
into the indicated position of a list.
\end{defun}

\begin{defun}[Function]
rest list

\cdf{rest} means the same as \cdf{cdr} but mnemonically complements \cdf{first}.
\cdf{setf} may be used with \cdf{rest} to replace the \emph{cdr} of a list
with a new value.
\end{defun}

\begin{defun}[Function]
nthcdr n list

\cd{(nthcdr \emph{n} \emph{list})} performs the \cdf{cdr} operation \emph{n} times
on \emph{list}, and returns the result.
For example:
\begin{lisp}
(nthcdr 0 '(a b c)) \EV\ (a b c) \\
(nthcdr 2 '(a b c)) \EV\ (c) \\
(nthcdr 4 '(a b c)) \EV\ {\emptylist}
\end{lisp}
In other words, it returns the \emph{n}th \emph{cdr} of the list.

\begin{lisp}
(car (nthcdr n x)) \EQ\ (nth n x)
\end{lisp}
The argument \emph{n} must be a non-negative integer.
\end{defun}

\begin{defun}[Function]
last list &optional (n 1)

\cdf{last} returns the tail of the \emph{list}
consisting of the last \emph{n} conses of \emph{list}.  The \emph{list} may
be a dotted list.  It is an error if the \emph{list} is circular.

The argument \emph{n} must be a non-negative integer.
If \emph{n} is zero, then the atom that terminates the \emph{list}
is returned.  If \emph{n} is not less than the number of cons cells
making up the \emph{list}, then the \emph{list} itself is returned.

For example:
\begin{lisp}
(setq x '(a b c d)) \\
(last x) \EV\ (d) \\
(rplacd (last x) '(e f)) \\
x \EV\ '(a b c d e f) \\
(last x 3) \EV\ (d e f) \\
(last '()) \EV\ () \\
(last '(a b c . d)) \EV\ (c . d) \\
(last '(a b c . d) 0) \EV\ d \\
(last '(a b c . d) 2) \EV\ (b c . d) \\
(last '(a b c . d) 1729) \EV\ (a b c . d)
\end{lisp}
\end{defun}

\begin{defun}[Function]
list &rest args

\cdf{list} constructs and returns a list of its arguments.
For example:
\begin{lisp}
(list 3 4 'a (car '(b . c)) (+ 6 -2)) \EV\ (3 4 a b 4)
\end{lisp}

\begin{lisp}
(list) \EV\ () \\
(list (list 'a 'b) (list 'c 'd 'e)) \EV\ ((a b) (c d e))
\end{lisp}
\end{defun}

\begin{defun}[Function]
list* arg &rest others

\cdf{list*} is like \cdf{list} except that the last \emph{cons}
of the constructed list is ``dotted.''  The last argument to \cdf{list*}
is used as the \emph{cdr} of the last cons constructed;
this need not be an atom.  If it is not an atom,
then the effect is to add several new elements to the front of a list.
For example:
\begin{lisp}
(list* 'a 'b 'c 'd) \EV\ (a b c . d)
\end{lisp}
This is like
\begin{lisp}
(cons 'a (cons 'b (cons 'c 'd)))
\end{lisp}
Also:
\begin{lisp}
(list* 'a 'b 'c '(d e f)) \EV\ (a b c d e f) \\*
(list* x) \EQ\ x
\end{lisp}
\end{defun}

\begin{defun}[Function]
make-list size &key :initial-element

This creates and returns a list containing \emph{size} elements, each
of which is initialized to the \cd{:initial-element}
argument (which defaults to {\false}).
\emph{size} should be a non-negative integer.
For example:
\begin{lisp}
(make-list 5) \EV\ ({\false} {\false} {\false} {\false} {\false}) \\
(make-list 3 \cd{:initial-element} 'rah) \EV\ (rah rah rah)
\end{lisp}
\end{defun}

\begin{defun}[Function]
append &rest lists

The arguments to \cdf{append} are lists.  The result is a list that is the
concatenation of the arguments.
The arguments are not destroyed.
For example:
\begin{lisp}
(append '(a b c) '(d e f) '{\emptylist} '(g)) \EV\ (a b c d e f g)
\end{lisp}
Note that \cdf{append} copies the top-level list structure of each of its
arguments \emph{except} the last.
The function \cdf{concatenate} can perform a similar operation, but always
copies all its arguments.  See also \cdf{nconc}, which is like \cdf{append}
but destroys all arguments but the last.

The last argument actually need not be a list but may be any Lisp object,
which becomes the tail end of the constructed list.
For example, \cd{(append '(a b c) 'd)} \EV\ \cd{(a b c . d)}.

\cd{(append \emph{x} '{\emptylist})} is an idiom once frequently used to copy the
list \emph{x}, but the \cdf{copy-list} function is more appropriate to this
task.
\end{defun}

\begin{defun}[Function]
copy-list list

This returns a list that is \cdf{equal} to \emph{list}, but not \cdf{eq}.
Only the top level of list structure is copied; that is, \cdf{copy-list}
copies in the \emph{cdr} direction but not in the \emph{car} direction.
If the list is ``dotted,'' that is, \cd{(cdr (last \emph{list}))}
is a non-{\nil} atom, this will be true of the returned list also.
See also \cdf{copy-seq} and \cdf{copy-tree}.
\end{defun}

\begin{defun}[Function]
copy-alist list

\cdf{copy-alist} is for copying association lists.  The top level of
list structure of \emph{list} is copied, just as for \cdf{copy-list}.
In addition, each element of \emph{list} that is a cons is replaced
in the copy by a new cons with the same \emph{car} and \emph{cdr}.
\end{defun}

\begin{defun}[Function]
copy-tree object

\cdf{copy-tree} is for copying trees of conses.
The argument \emph{object} may be any Lisp object.
If it is not a cons, it is returned; otherwise
the result is a new cons of the results of calling \cdf{copy-tree}
on the \emph{car} and \emph{cdr} of the argument.  In other words,
all conses in the tree are copied recursively, stopping
only when non-conses are encountered.
Circularities and the sharing of substructure are \emph{not} preserved.
\end{defun}

\begin{defun}[Function]
revappend x y

\cd{(revappend \emph{x} \emph{y})} is exactly the same as 
\cd{(append (reverse \emph{x}) \emph{y})} except that it is potentially more
efficient.  Both \emph{x} and \emph{y} should be lists.
The argument \emph{x} is copied, not destroyed.
Compare this with \cdf{nreconc}, which destroys its first argument.
\end{defun}

\begin{defun}[Function]
nconc &rest lists

\cdf{nconc} takes lists as arguments.  It returns a list that is the arguments
concatenated together.  The arguments are changed rather than copied.
(Compare this with \cdf{append}, which copies arguments rather than
destroying them.)
For example:
\begin{lisp}
(setq x '(a b c)) \\
(setq y '(d e f)) \\
(nconc x y) \EV\ (a b c d e f) \\
x \EV\ (a b c d e f)
\end{lisp}
Note, in the example, that the value of \cdf{x} is now different,
since its last cons has been \cdf{rplacd}'d to the value of \cdf{y}.
If one were then to evaluate \cd{(nconc x y)} again,
it would yield a piece of ``circular'' list
structure, whose printed representation would be
\cd{(a b c d e f d e f d e f ...)}, repeating forever;
if the \cdf{*print-circle*} switch were non-{\nil},
it would be printed as \cd{(a b c . \#1=(d e f . \#1\#))}.

The side-effect behavior of \cdf{nconc} is specified by a recursive relationship
outlined in the following table, in which a call to \cdf{nconc} matching
the earliest possible
pattern on the left is required to have side-effect behavior
equivalent to the corresponding expression on the right.
\begin{flushleft}
\begin{tabular}{@{}ll@{}}
\cd{(nconc)}&\cd{nil~~~~~;}\textrm{No side effects} \\
\cd{(nconc nil . \emph{r})~~~~}&\cd{(nconc . \emph{r})} \\
\cd{(nconc \emph{x})}&\emph{x} \\
\cd{(nconc \emph{x} \emph{y})}&\cd{(let ((p \emph{x}) (q \emph{y}))} \\
                                  &\cd{~~(rplacd (last p) q)} \\
                                  &\cd{~~p)} \\
\cd{(nconc \emph{x} \emph{y} . \emph{r})}&\cd{(nconc (nconc \emph{x} \emph{y})
  . \emph{r})}
\end{tabular} 
\end{flushleft}
\end{defun}

\begin{defun}[Function]
nreconc x y

\cd{(nreconc \emph{x} \emph{y})} is exactly the same as 
\cd{(nconc (nreverse \emph{x}) \emph{y})} except that it is potentially more
efficient.  Both \emph{x} and \emph{y} should be lists.
The argument \emph{x} is destroyed.
Compare this with \cdf{revappend}.

\begin{lisp}
(setq planets '(jupiter mars earth venus mercury)) \\
(setq more-planets '(saturn uranus pluto neptune)) \\
(nreconc more-planets planets) \\
\`\EV\ (neptune pluto uranus saturn jupiter mars earth venus mercury) \\
~~\textrm{and now the value of \cdf{more-planets} is not well defined}
\end{lisp}

\cd{(nreconc \emph{x} \emph{y})} is permitted and
required to have side-effect behavior
equivalent to that of \cd{(nconc (nreverse \emph{x})~\emph{y})}.
\end{defun}

\begin{defmac}
push item place

The form \emph{place} should be the name of a generalized variable
containing a list; \emph{item} may refer to any Lisp object.  The \emph{item}
is consed onto the front of the list, and the augmented list is stored
back into \emph{place} and returned.
The form \emph{place} may be any form acceptable as a
generalized variable to \cdf{setf}.  If the list held in \emph{place} is
viewed as a push-down stack, then \cdf{push} pushes an element onto the top
of the stack.
For example:
\begin{lisp}
(setq x '(a (b c) d)) \\
(push 5 (cadr x)) \EV\ (5 b c)  \textrm{and now} x \EV\ (a (5 b c) d)
\end{lisp}
The effect of \cd{(push \emph{item} \emph{place})}
is roughly equivalent to
\begin{lisp}
(setf \emph{place} (cons \emph{item} \emph{place}))
\end{lisp}
except that the latter would evaluate any subforms of \emph{place}
twice, while \cdf{push} takes care to evaluate them only once.
Moreover, for certain \emph{place} forms \cdf{push} may be
significantly more efficient than the \cdf{setf} version.

Note that \emph{item} is fully evaluated before any part of \emph{place}
is evaluated.
\end{defmac}

\begin{defmac}
pushnew item place &key :test :test-not :key

The form \emph{place} should be the name of a generalized variable
containing a list; \emph{item} may refer to any Lisp object.  If the
\emph{item} is not already a member of the list (as determined by
comparisons using the \cd{:test} predicate, which defaults to \cdf{eql}),
then the \emph{item} is consed onto the front of the list, and
the augmented list is stored back into \emph{place} and returned; otherwise
the unaugmented list is returned.  The form \emph{place} may be
any form acceptable as a generalized variable to \cdf{setf}.  If the
list held in \emph{place} is viewed as a set, then \cdf{pushnew} adjoins an
element to the set; see \cdf{adjoin}.

The keyword arguments to \cdf{pushnew}
follow the conventions for the generic sequence
functions.  See chapter~\ref{KSEQUE}.
In effect, these keywords are simply passed on to the \cdf{adjoin} function.

\cdf{pushnew} returns the new contents of the \emph{place}.
For example:
\begin{lisp}
(setq x '(a (b c) d)) \\
(pushnew 5 (cadr x)) \EV\ (5 b c)   \textrm{and now} x \EV\ (a (5 b c) d) \\
(pushnew 'b (cadr x)) \EV\ (5 b c)  \textrm{and \cdf{x} is unchanged}
\end{lisp}
The effect of
\begin{lisp}
(pushnew \emph{item} \emph{place} \cd{:test} \emph{p})
\end{lisp}
is roughly equivalent to
\begin{lisp}
(setf \emph{place} (adjoin \emph{item} \emph{place} \cd{:test} \emph{p}))
\end{lisp}
except that the latter would evaluate any subforms of
\emph{place} twice, while \cdf{pushnew} takes care to evaluate them only once.
Moreover, for certain \emph{place} forms \cdf{pushnew} may be
significantly more efficient than the \cdf{setf} version.

Note that \emph{item} is fully evaluated before any part of \emph{place}
is evaluated.
\end{defmac}

\begin{defmac}
pop place

The form \emph{place} should be the name of a generalized variable
containing a list.  The result of \cdf{pop} is the \cdf{car} of the contents
of \emph{place}, and as a side effect the \cdf{cdr} of the contents is stored
back into \emph{place}.  The form \emph{place} may be any form acceptable as a
generalized variable to \cdf{setf}.  If the list held in \emph{place} is
viewed as a push-down stack, then \cdf{pop} pops an element from the top of
the stack and returns it.
For example:
\begin{lisp}
(setq stack '(a b c)) \\
(pop stack) \EV\ a  \textrm{and now} stack \EV\ (b c)
\end{lisp}
The effect of \cd{(pop \emph{place})} is roughly equivalent to
\begin{lisp}
(prog1 (car \emph{place}) (setf \emph{place} (cdr \emph{place})))
\end{lisp}
except that the latter would evaluate any subforms of \emph{place}
three times, while \cdf{pop} takes care to evaluate them only once.
Moreover, for certain \emph{place} forms \cdf{pop} may be
significantly more efficient than the \cdf{setf} version.
\end{defmac}

\begin{defun}[Function]
butlast list &optional n

This creates and returns a list with the same elements as \emph{list},
excepting the last \emph{n} elements.
\emph{n} defaults to 1.  The argument is not destroyed.
If the \emph{list} has fewer than \emph{n} elements, then {\emptylist} is returned.
For example:
\begin{lisp}
(butlast '(a b c d)) \EV\ (a b c) \\
(butlast '((a b) (c d))) \EV\ ((a b)) \\
(butlast '(a)) \EV\ {\emptylist} \\
(butlast nil) \EV\ {\emptylist}
\end{lisp}
The name is from the phrase ``all elements but the last.''
\end{defun}

\begin{defun}[Function]
nbutlast list &optional n

This is the destructive version of \cdf{butlast}; it changes the \emph{cdr} of
the cons \emph{n}+1 from the end of the \emph{list} to {\nil}.  \emph{n} defaults to 1.
If the \emph{list} has fewer than \emph{n} elements, then \cdf{nbutlast}
returns {\emptylist}, and the argument is not modified.  (Therefore
one normally writes \cd{(setq a (nbutlast a))} rather than simply
\cd{(nbutlast a)}.)
For example:
\begin{lisp}
(setq foo '(a b c d)) \\
(nbutlast foo) \EV\ (a b c) \\
foo \EV\ (a b c) \\
(nbutlast '(a)) \EV\ {\emptylist} \\
(nbutlast '{\nil}) \EV\ {\emptylist}
\end{lisp}
\end{defun}

\begin{defun}[Function]
ldiff list sublist

\emph{list} should be a list, and \emph{sublist} should be a sublist
of \emph{list}, that is, one of the conses that make up \emph{list}.
\cdf{ldiff} (meaning ``list difference'') will return a new (freshly consed)
list, whose elements are those elements of \emph{list} that appear before
\emph{sublist}.  If \emph{sublist} is not a tail of \emph{list}
(and in particular if \emph{sublist} is {\nil}),
then a copy of the entire \emph{list} is returned.
The argument \emph{list} is not destroyed.
For example:
\begin{lisp}
(setq x '(a b c d e)) \\
(setq y (cdddr x)) \EV\ (d e) \\
(ldiff x y) \EV\ (a b c) \\[4pt]
\textrm{but} (ldiff '(a b c d) '(c d)) \EV\ (a b c d)
\end{lisp}
since the sublist was not \cdf{eq} to any part of the list.
\end{defun}

\section{Alteration of List Structure}

The functions \cdf{rplaca} and \cdf{rplacd}
may be used to make alterations in already existing
list structure, that is, to change the \emph{car} or \emph{cdr} of an
existing cons.
One may also use \cdf{setf} in conjunction with \cdf{car} and \cdf{cdr}.

The structure is not copied but is destructively altered;
hence caution should be exercised when using these functions, as
strange side effects can occur if portions of list structure become
shared.
The \cdf{nconc}, \cdf{nreverse}, \cdf{nreconc},
and \cdf{nbutlast} functions, already
described,
have the same property, as do certain of the generic sequence
functions such as \cdf{delete}.
However, they are normally not
used for this side effect; rather, the list-structure modification
is purely for efficiency, and compatible non-modifying functions
are provided.

\begin{defun}[Function]
rplaca x y

\cd{(rplaca \emph{x} \emph{y})} changes the \emph{car} of \emph{x} to \emph{y} and returns
(the modified) \emph{x}.  \emph{x} must be a cons, but \emph{y} may be any
Lisp object.
For example:
\begin{lisp}
(setq g '(a b c)) \\
(rplaca (cdr g) 'd) \EV\ (d c) \\
\textrm{Now} g \EV\ (a d c)
\end{lisp}
\end{defun}

\begin{defun}[Function]
rplacd x y

\cd{(rplacd \emph{x} \emph{y})} changes the \emph{cdr} of \emph{x} to \emph{y} and returns
(the modified) \emph{x}.  \emph{x} must be a cons, but \emph{y} may be
any Lisp object.
For example:
\begin{lisp}
(setq x '(a b c)) \\
(rplacd x 'd) \EV\ (a . d) \\
\textrm{Now} x \EV\ (a . d)
\end{lisp}
\end{defun}

The functions \cdf{rplaca} and \cdf{rplacd} go back to the earliest
origins of Lisp, along with \cdf{car}, \cdf{cdr}, and \cdf{cons}.
Nowadays, however, they seem to be falling by the wayside.
More and more Common Lisp programmers use \cdf{setf} for nearly
all structure modifications: \cd{(rplaca x~y)} is rendered
as \cd{(setf (car x)~y)} or perhaps as \cd{(setf (first x)~y)}.
Even more likely is that a \cdf{defstruct} structure or a CLOS class
is used in place of a list, if the data structure is at all complicated;
in this case \cdf{setf} is used with a slot accessor.

\section{Substitution of Expressions}

\indexterm{substitution}
A number of functions are provided for performing substitutions
within a tree.  All take a tree and a description
of old subexpressions to be replaced by new ones.
They come in non-destructive and destructive varieties
and specify substitution either by two arguments or by an association list.

The naming conventions for these functions and for their keyword
arguments generally follow the conventions for the generic sequence
functions.  See chapter~\ref{KSEQUE}.

\begin{defun}[Function]
subst new old tree &key :test :test-not :key \\
subst-if new test tree &key :key \\
subst-if-not new test tree &key :key

\cd{(subst \emph{new} \emph{old} \emph{tree})} makes a copy of \emph{tree},
substituting \emph{new} for every subtree or leaf of \emph{tree}
(whether the subtree or leaf is a \emph{car} or a \emph{cdr} of its parent)
such that \emph{old} and the subtree or leaf satisfy the test.  It
returns the modified copy of \emph{tree}.  The original \emph{tree} is
unchanged, but the result tree may share with parts of the argument
\emph{tree}.

For example:
\begin{lisp}
(subst 'tempest 'hurricane \\
~~~~~~~'(shakespeare wrote (the hurricane))) \\
~~~\EV\ (shakespeare wrote (the tempest)) \\
\\
(subst 'foo '{\nil} '(shakespeare wrote (twelfth night))) \\
~~~\EV\ (shakespeare wrote (twelfth night . foo) . foo) \\
\\
(subst '(a . cons) '(old . pair) \\
~~~~~~~'((old . spice) ((old . shoes) old . pair) (old . pair)) \\
~~~~~~~\cd{:test} \#'equal) \\
~~~\EV\ ((old . spice) ((old . shoes) a . cons) (a . cons))
\end{lisp}
This function is not destructive; that is, it does not change
the \emph{car} or \emph{cdr} of any already existing list structure.
One possible definition of \cdf{subst}:
\begin{lisp}
(defun subst (old new tree \cd{\&rest} x \cd{\&key} test test-not key) \\*
~~(cond ((satisfies-the-test old tree :test test \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~:test-not test-not :key key) \\*
~~~~~~~~~new) \\*
~~~~~~~~((atom tree) tree) \\
~~~~~~~~(t (let ((a (apply \#'subst old new (car tree) x)) \\*
~~~~~~~~~~~~~~~~~(d (apply \#'subst old new (cdr tree) x))) \\
~~~~~~~~~~~~~(if (and (eql a (car tree)) \\*
~~~~~~~~~~~~~~~~~~~~~~(eql d (cdr tree))) \\*
~~~~~~~~~~~~~~~~~tree \\*
~~~~~~~~~~~~~~~~~(cons a d))))))
\end{lisp}
See also \cdf{substitute}, which substitutes for top-level elements
of a sequence.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\begin{defun}[Function]
nsubst new old tree &key :test :test-not :key \\
nsubst-if new test tree &key :key \\
nsubst-if-not new test tree &key :key

\cdf{nsubst} is a destructive version of \cdf{subst}.  The list structure of
\emph{tree} is altered by destructively replacing with \emph{new}
each leaf or subtree of the \emph{tree} such that \emph{old} and the leaf
or subtree satisfy the test.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\begin{defun}[Function]
sublis alist tree &key :test :test-not :key

\cdf{sublis} makes substitutions for objects in a tree
(a structure of conses).
The first argument to \cdf{sublis} is an association list.
The second argument is the tree in which
substitutions are to be made, as for \cdf{subst}.
\cdf{sublis} looks at all subtrees and leaves of the tree;
if a subtree or leaf appears as a key in the association
list (that is, the key and the subtree or leaf satisfy the test),
it is replaced by the object with which it is associated.
This operation is non-destructive.  In effect, \cdf{sublis} can
perform several \cdf{subst} operations simultaneously.
For example:
\begin{lisp}
(sublis '((x . 100) (z . zprime)) \\*
~~~~~~~~'(plus x (minus g z x p) 4 . x)) \\*
~~~\EV\ (plus 100 (minus g zprime 100 p) 4 . 100) \\*
 \\*
(sublis '(((+ x y) . (- x y)) ((- x y) . (+ x y))) \\*
~~~~~~~~'(* (/ (+ x y) (+ x p)) (- x y)) \\*
~~~~~~~~:test \#'equal) \\*
~~~\EV\ (* (/ (- x y) (+ x p)) (+ x y))
\end{lisp}

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\begin{defun}[Function]
nsublis alist tree &key :test :test-not :key

\cdf{nsublis} is like \cdf{sublis} but destructively modifies the relevant
parts of the \emph{tree}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\section{Using Lists as Sets}

Common Lisp includes functions that allow a list of items to be
treated as a \emph{set}.
There are functions to add, remove, and search for items in a list,
based on various criteria.
There are also set union, intersection, and difference functions.

The naming conventions for these functions and for their keyword
arguments generally follow the conventions that apply to the generic sequence
functions.  See chapter~\ref{KSEQUE}.

\begin{defun}[Function]
member item list &key :test :test-not :key \\
member-if predicate list &key :key \\
member-if-not predicate list &key :key

The \emph{list} is searched for an element that satisfies the test.
If none is found, {\false} is returned;
otherwise, the tail of \emph{list} beginning
with the first element that satisfied the test is returned.
The \emph{list} is searched on the top level only. 
These functions are suitable for use as predicates.

For example:
\begin{lisp}
(member 'snerd '(a b c d)) \EV\ {\false} \\
(member-if \#'numberp '(a \#{\Xbackslash}Space 5/3 foo)) \EV\ (5/3 foo) \\
(member 'a '(g (a y) c a d e a f)) \EV\ (a d e a f)
\end{lisp}
Note, in the last example,
that the value returned by \cdf{member} is \cdf{eq} to the portion of the list
beginning with \cdf{a}.
Thus \cdf{rplaca} on the result of \cdf{member} may be used
to alter the found list element,
if a check is first made that \cdf{member} did not return {\false}.

See also \cdf{find} and \cdf{position}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\begin{defun}[Function]
tailp sublist list

\cdf{tailp} is true if and only if there exists an integer \emph{n} such that
\begin{lisp}
(eql \emph{sublist} (nthcdr \emph{n} \emph{list}))
\end{lisp}
\emph{list} may be a dotted list (implying that
implementations must use \cdf{atom} and not \cdf{endp} to check for
the end of the \emph{list}).
\end{defun}

\begin{defun}[Function]
adjoin item list &key :test :test-not :key

\cdf{adjoin} is used to add an element to a set, provided that
it is not already a member.  The equality test defaults to \cdf{eql}.
\begin{lisp}
(adjoin \emph{item} \emph{list}) \EQ\ (if (member \emph{item} \emph{list}) \emph{list} (cons \emph{item} \emph{list}))
\end{lisp}
In general, the test may be any predicate; the \emph{item} is added to the
list only if there is no element of the list that ``satisfies the test.''

\cdf{adjoin} deviates from the usual rules described in chapter~\ref{KSEQUE}
for the treatment of arguments named \emph{item} and \cd{:key}.
If a \cd{:key} function is specified, it is applied to \emph{item}
as well as to each element of the list.  The rationale is that
if the \emph{item} is not yet in the list, it soon will be, and so
the test is more properly viewed as being between two elements
rather than between a separate \emph{item} and an element.
\begin{lisp}
(adjoin \emph{item} \emph{list} :key \emph{fn}) \\
~~\EQ\ (if (member (funcall \emph{fn} \emph{item}) \emph{list}
  :key \emph{fn}) \emph{list} (cons \emph{item} \emph{list})) 
\end{lisp}
See \cdf{pushnew}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\begin{defun}[Function]
union list1 list2 &key :test :test-not :key \\
nunion list1 list2 &key :test :test-not :key

\cdf{union} takes two lists and returns a new list containing
everything that is an element of either of the \emph{lists}.
If there is a duplication between two lists,
only one of the duplicate instances will be in the result.
If either of the arguments has duplicate entries within it,
the redundant entries
may or may not appear in the result.
For example:
\begin{lisp}
(union '(a b c) '(f a d)) \\
~~~\EV\ (a b c f d) \textrm{or} (b c f a d) \textrm{or} (d f a b c) \textrm{or} ... \\
 \\
(union '((x 5) (y 6)) '((z 2) (x 4)) :key \#'car) \\
~~~\EV\ ((x 5) (y 6) (z 2)) \textrm{or} ((x 4) (y 6) (z 2)) \textrm{or} ...
\end{lisp}

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be \cdf{eq} to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the union operation may be
described as follows.  For all possible ordered pairs consisting of one
element from \emph{list1} and one element from \emph{list2}, the test is used
to determine whether they ``match.''  For every matching pair, at least
one of the two elements of the pair will be in the result.  Moreover, any
element from either list that matches no element of the other will appear
in the result.  All this is very general, but probably not particularly
useful unless the test is an equivalence relation.

The \cd{:test-not} argument can be useful when the test function
is the logical negation of an equivalence test.  A good example
of this is the function \cdf{mismatch}, which is logically inverted
so that possibly useful information can be returned if the arguments do not
match.  This additional ``useful information'' is discarded in the following
example; \cdf{mismatch} is used purely as a predicate.
\begin{lisp}
(union '(\#(a b) \#(5 0 6) \#(f 3)) \\
~~~~~~~'(\#(5 0 6) (a b) \#(g h)) \\
~~~~~~~:test-not \\
~~~~~~~\#'mismatch) \\
~~~\EV\ (\#(a b) \#(5 0 6) \#(f 3) \#(g h))~~~~~;\textrm{One possible result} \\
~~~\EV\ ((a b) \#(f 3) \#(5 0 6) \#(g h))~~~~~~;\textrm{Another possible result}
\end{lisp}
Using \cd{\cd{:test-not} \#'mismatch} differs from using
\cd{\cd{:test} \#'equalp}, for example, because \cdf{mismatch}
will determine that \cd{\#(a b)} and \cd{(a b)} are the same,
while \cdf{equalp} would regard them as not the same.

\cdf{nunion} is the destructive version of \cdf{union}.
It performs the same operation but may destroy the argument lists,
perhaps in order to use their cells to construct the result.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations;
\cdf{nunion} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of 
any of the argument lists.
\end{newer}
\end{defun}

\begin{defun}[Function]
intersection list1 list2 &key :test :test-not :key \\
nintersection list1 list2 &key :test :test-not :key

\cdf{intersection} takes two lists and returns a new list containing
everything that is an element of both argument lists.
If either list has duplicate entries, the redundant entries
may or may not appear in the result.
For example:
\begin{lisp}
(intersection '(a b c) '(f a d)) \EV\ (a)
\end{lisp}
There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be \cdf{eq} to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the intersection operation
may be described as follows.  For all possible ordered pairs consisting of
one element from \emph{list1} and one element from \emph{list2}, the test is
used to determine whether they ``match.''  For every matching pair,
exactly one of the two elements of the pair will be put in the result.
No element from either list appears in the result that does not match
an element from the other list.
All this is very general, but probably
not particularly useful unless the test is an equivalence relation.

\cdf{nintersection} is the destructive version of \cdf{intersection}.
It performs the same operation, but may destroy \emph{list1},
perhaps in order to use its cells to construct the result.
(The argument \emph{list2} is \emph{not} destroyed.)

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations;
\cdf{nintersection} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of 
any of the argument lists.
\end{newer}
\end{defun}

\begin{defun}[Function]
set-difference list1 list2 &key :test :test-not :key \\
nset-difference list1 list2 &key :test :test-not :key

\cdf{set-difference} returns a list of elements of \emph{list1}
that do not appear in \emph{list2}.  This operation is
not destructive.

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be \cdf{eq} to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the set difference operation
may be described as follows.  For all possible ordered pairs consisting of
one element from \emph{list1} and one element from \emph{list2}, the test is
used to determine whether they ``match.''  An element of \emph{list1}
appears in the result if and only if it does not match any element
of \emph{list2}. This is very general and permits interesting applications.
For example, one can remove from a list of strings all those strings
containing one of a given list of characters:
\begin{lisp}
;; Remove all flavor names that contain "c" or "w". \\
(set-difference '("strawberry" "chocolate" "banana" \\
~~~~~~~~~~~~~~~~~~"lemon" "pistachio" "rhubarb") \\
~~~~~~~~~~~~~~~~'(\#{\Xbackslash}c \#{\Xbackslash}w) \\
~~~~~~~~~~~~~~~~:test \\
~~~~~~~~~~~~~~~~\#'(lambda (s c) (find c s))) \\
~~~\EV\ ("banana" "rhubarb" "lemon")~~~~~;\textrm{One possible ordering}
\end{lisp}

\cdf{nset-difference} is the destructive version of \cdf{set-difference}.
This operation may destroy \emph{list1}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\begin{defun}[Function]
set-exclusive-or list1 list2 &key :test :test-not :key \\
nset-exclusive-or list1 list2 &key :test :test-not :key

\cdf{set-exclusive-or} returns a list of elements that appear
in exactly one of \emph{list1} and \emph{list2}.
This operation is not destructive.

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be \cdf{eq} to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the \cdf{set-exclusive-or} operation
may be described as follows.  For all possible ordered pairs consisting of
one element from \emph{list1} and one element from \emph{list2}, the test is
used to determine whether they ``match.''  The result contains precisely
those elements of \emph{list1} and \emph{list2} that appear in no matching pair.

\cdf{nset-exclusive-or} is the destructive version of \cdf{set-exclusive-or}.
Both lists may be destroyed in producing the result.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations;
\cdf{nset-exclusive-or} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of 
any of the argument lists.
\end{newer}
\end{defun}

\begin{defun}[Function]
subsetp list1 list2 &key :test :test-not :key

\cdf{subsetp} is a predicate that is true if every element of \emph{list1}
appears in (``matches'' some element of) \emph{list2}, and false otherwise.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\section{Association Lists}

An \emph{association list}, or \emph{a-list}, is a data structure
used very frequently in Lisp.  An a-list is a list of pairs (conses);
each pair is an association.  The \emph{car} of a pair is called the \emph{key},
and the \emph{cdr} is called the \emph{datum}.

An advantage of the a-list representation is that an a-list can be
incrementally augmented simply by adding new entries to the front.
Moreover, because the searching function \cdf{assoc} searches the
a-list in order, new entries can ``shadow'' old entries.  If an a-list is
viewed as a mapping from keys to data, then the mapping can be not only
augmented but also altered in a non-destructive manner by adding new
entries to the front of the a-list.

Sometimes an a-list represents a bijective mapping, and it is desirable
to retrieve a key given a datum.  For this purpose, the ``reverse'' searching
function \cdf{rassoc} is provided.  Other variants of a-list searches
can be constructed using the function \cdf{find} or \cdf{member}.

It is permissible to let {\false} be an element of an a-list in place of
a pair.  Such an element is not considered to be a pair but is simply
passed over when the a-list is searched by \cdf{assoc}.

\begin{defun}[Function]
acons key datum a-list

\cdf{acons} constructs a new association list by adding the pair
\cd{(\emph{key} . \emph{datum})} to the old \emph{a-list}.
\begin{lisp}
(acons x y a) \EQ\ (cons (cons x y) a)
\end{lisp}
\end{defun}

\begin{defun}[Function]
pairlis keys data &optional a-list

\cdf{pairlis} takes two lists and makes an association list that associates
elements of the first list to corresponding elements of the second
list.  It is an error if the two lists \emph{keys} and \emph{data} are not of
the same length.  If the optional argument \emph{a-list} is provided, then the
new pairs are added to the front of it.

The new pairs may appear in the resulting a-list in any order;
in particular, either forward or backward order is permitted.
Therefore the result of the call
\begin{lisp}
(pairlis '(one two) '(1 2) '((three . 3) (four . 19)))
\end{lisp}
might be
\begin{lisp}
((one . 1) (two . 2) (three . 3) (four . 19))
\end{lisp}
but could equally well be
\begin{lisp}
((two . 2) (one . 1) (three . 3) (four . 19))
\end{lisp}
\end{defun}

\begin{defun}[Function]
assoc item a-list &key :test :test-not :key \\
assoc-if predicate a-list &key :key \\
assoc-if-not predicate a-list &key :key

Each of these searches the association list
\emph{a-list}.  The value is the first pair in the a-list such that
the \emph{car} of the pair satisfies the test, or {\false} if there is
no such pair in the a-list.
For example:
\begin{lisp}
(assoc 'r '((a . b) (c . d) (r . x) (s . y) (r . z))) \\
~~~~~~~~\EV\  (r . x) \\
(assoc 'goo '((foo . bar) (zoo . goo))) \EV\ {\false} \\
(assoc '2 '((1 a b c) (2 b c d) (-7 x y z))) \EV\ (2 b c d)
\end{lisp}
It is possible to \cdf{rplacd} the result of \cdf{assoc} \emph{provided}
that it is not {\false},
in order to ``update'' the ``table'' that was \cdf{assoc}'s second argument.
(However, it is often better to update an a-list by adding new pairs
to the front, rather than altering old pairs.)
For example:
\begin{lisp}
(setq values '((x . 100) (y . 200) (z . 50))) \\
(assoc 'y values) \EV\ (y . 200) \\
(rplacd (assoc 'y values) 201) \\
(assoc 'y values) \EV\ (y . 201) \textrm{now}
\end{lisp}
A typical trick is to say
\cd{(cdr (assoc x y))}.
Because the \emph{cdr} of {\false} is guaranteed to be {\false},
this yields {\false} if no pair is found \emph{or} if a pair is
found whose \emph{cdr} is {\false}.  This is useful if {\false} serves
its usual role as a ``default value.''

The two expressions
\begin{lisp}
(assoc \emph{item} \emph{list} :test \emph{fn})
\end{lisp}
and
\begin{lisp}
(find \emph{item} \emph{list} :test \emph{fn} :key \#'car)
\end{lisp}
are equivalent in meaning with one important exception:
if {\nil} appears in the a-list in place of a pair,
and the \emph{item} being searched for is {\nil},
\cdf{find} will blithely compute the \emph{car} of the {\nil} in the a-list,
find that it is equal to the \emph{item}, and return {\nil},
whereas \cdf{assoc} will ignore the {\nil} in the a-list and continue
to search for an actual pair (cons) whose \emph{car} is {\nil}.
See \cdf{find} and \cdf{position}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\begin{defun}[Function]
rassoc item a-list &key :test :test-not :key \\
rassoc-if predicate a-list &key :key \\
rassoc-if-not predicate a-list &key :key

\cdf{rassoc} is the reverse form of \cdf{assoc}; it searches for
a pair whose \emph{cdr} satisfies the test, rather than the \emph{car}.
If the \emph{a-list} is considered to be a mapping, then \cdf{rassoc}
treats the \emph{a-list} as representing the inverse mapping.
For example:
\begin{lisp}
(rassoc 'a '((a . b) (b . c) (c . a) (z . a))) \EV\ (c . a)
\end{lisp}

The expressions
\begin{lisp}
(rassoc \emph{item} \emph{list} :test \emph{fn})
\end{lisp}
and
\begin{lisp}
(find \emph{item} \emph{list} :test \emph{fn} :key \#'cdr)
\end{lisp}
are equivalent in meaning, except when the \emph{item} is {\nil}
and {\nil} appears in place of a pair in the a-list.  See the discussion
of the function \cdf{assoc}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

%RUSSIAN
\else

\chapter{Списки}

\emph{cons}-ячейка, или пара с точкой, является составным объектом данных,
содержащим два элемента: \emph{car} и \emph{cdr}. И \emph{car} и \emph{cdr}
могут быть любым Lisp'овым объектом.
\emph{Список (list)} является цепочкой cons-ячеек, соединённых \emph{cdr}
элементами.
Цепочка завершается некоторым не-cons объектом (atom object).
Обычный список завершается объектом {\nil}, или, как его ещё называют, пустым
списком {\emptylist}.
Список, цепочка которого завершается некоторым не-{\nil} объектом, называется
\emph{списком с точкой}.

Для проверки конца списка служит предикат \cdf{endp}.

\section{Cons-ячейки}

Ниже представлены несколько основных операций над cons-ячейками. В данных
случаях cons-ячейки рассматриваются как пары, а не компоненты списка.

\begin{defun}[Функция]
car list

Функция возвращает \emph{car} элемент списка \emph{list}, который должен быть
или \emph{cons}-ячейкой или {\emptylist}. То есть аргумент должен удовлетворять
предикату \cdf{listp}.
По определению \emph{car} элемент пустого списка является пустым списком.
Если cons-ячейка является первым звеном списке, то можно сказать, что \cdf{car}
возвращает первый элемент списка.
Например:
\begin{lisp}
(car '(a b c)) \EV\ a
\end{lisp}
Смотрите \cdf{first}.

\emph{car} элемент cons-ячейки может быть изменён с помощью \cdf{rplaca} или
\cdf{setf}.
\end{defun}

\begin{defun}[Функция]
cdr list

Функция возвращает \emph{cdr} элемент списка \emph{list}, который должен быть
или \emph{cons} ячейкой или {\emptylist}. То есть аргумент должен удовлетворять
предикату \cdf{listp}.
По определению \emph{cdr} элемент пустого списка является пустым списком.
Если cons-ячейка является первым звеном списке, то можно сказать, что \cdf{cdr}
возвращает остаток исходного списка без первого элемента.
Например:
\begin{lisp}
(cdr '(a b c)) \EV\ (b c)
\end{lisp}
Смотрите \cdf{rest}.

\emph{cdr} элемент cons-ячейки может быть изменён с помощью \cdf{rplacd} или
\cdf{setf}.
\end{defun}

\begin{defun}[Функция]
caar list \\
cadr list \\
cdar list \\
cddr list \\
caaar list \\
caadr list \\
cadar list \\
caddr list \\
cdaar list \\
cdadr list \\
cddar list \\
cdddr list \\
caaaar list \\
caaadr list \\
caadar list \\
caaddr list \\
cadaar list \\
cadadr list \\
caddar list \\
cadddr list \\
cdaaar list \\
cdaadr list \\
cdadar list \\
cdaddr list \\
cddaar list \\
cddadr list \\
cdddar list \\
cddddr list

Все композиции до четырёх \cdf{car} и \cdf{cdr} операций определены как
самостоятельные функции.
Их имена начинаются с \cdf{c} и заканчиваются \cdf{r}. Середина имени содержит
последовательность букв \cdf{a} и \cdf{d} в соответствие с композиций выполняемых
этими функциями.
Например:
\begin{lisp}
(cddadr x) \textrm{is the same as} (cdr (cdr (car (cdr x))))
\end{lisp}
Если в качестве аргумента указан список, тогда \cdf{cadr} вернёт второй элемент
списка, \cdf{caddr} --- третий, и \cdf{cadddr} --- четвёртый. Если первый
элемент списка является списком, тогда \cdf{caar} вернёт первый элемент этого
подсписка, \cdf{cdar} --- остаток подсписка без первого элемента, \cdf{cadar} --- второй
элемент подсписка и так далее.

В целях стиля, предпочтительнее определить функцию или макрос для
доступа к части сложной структуры данных, а не использовать длинные
\cdf{car}/\cdf{cdr} строки. Например, можно определить макрос для получения
списка параметров лямбда-выражения:
\begin{lisp}
(defmacro lambda-vars (lambda-exp) `(cadr ,lambda-exp))
\end{lisp}
и затем использовать \cdf{lambda-vars} вместо \cdf{cadr}.
Смотрите также \cdf{defstruct}, которая будет автоматически определять новые
типы данных и функции доступа к частям экземпляров этих структур.

Любая из этих функций может использоваться в связке с \cdf{setf}.
\end{defun}
	
\begin{defun}[Функция]
cons x y

\cdf{cons} является (примитивной) функцией для создания новой
\emph{cons}-ячейки, у которой \emph{car} элемент будет \emph{x}, а \emph{cdr}
элемент --- \emph{y}.
Например:
\begin{lisp}
(cons 'a 'b) \EV\ (a . b) \\
(cons 'a (cons 'b (cons 'c '{\emptylist}))) \EV\ (a b c) \\
(cons 'a '(b c d)) \EV\ (a b c d)
\end{lisp}
\cdf{cons} может рассматриваться как для создания \emph{cons}-ячейки, так и для
добавления нового элемента в начало списка.
\end{defun}

\begin{defun}[Функция]
tree-equal x y &key :test :test-not

Данный предикат истинен, если \emph{x} и \emph{y} являются изоморфными деревьями
с идентичными листьями, то есть, если \emph{x} и \emph{y} являются атомами,
которые удовлетворяют проверке (по-умолчанию \cdf{eql}),
или если они оба являются cons-ячейками и их \emph{car} элементы удовлетворяют
\cdf{tree-equal} и \emph{cdr} элементы удовлетворяют \cdf{tree-equal}.
Таким образом \cdf{tree-equal} рекурсивно сравнивает cons-ячейки (но не любой
другой составной объект). Смотрите \cdf{equal}, который рекурсивно сравнивает
другие составные объекты, как например строки.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\section{Списки}

Следующие функции выполняет различные операции над списками.

Список является одним из первых Lisp'овых типов данных. Имя <<Lisp>>
расшифровывается
как <<LISt Processing>>.

\begin{defun}[Функция]
endp object

Предикат \cdf{endp} используется для проверки конца списка. Возвращает ложь для
cons-ячеек, истину для {\nil}, и генерирует ошибку для всех остальных объектов
других типов.

\beforenoterule
\begin{implementation}
Implementations are encouraged to signal an
error, especially in the interpreter, for a non-list argument.
The \cdf{endp} function is defined so as to allow compiled code
to perform simply an atom check or a null check if speed is more
important than safety.
\end{implementation}
\afternoterule
\end{defun}

\begin{defun}[Функция]
list-length list

\cdf{list-length} возвращает длину списка \emph{list}.
\cdf{list-length} отличается от \cdf{length} при использовании с циклическим
списком. В таком случае \cdf{length} может не вернуть управление, тогда как
\cdf{list-length} вернёт {\nil}.
Например:
\begin{lisp}
(list-length '{\emptylist}) \EV\ 0 \\
(list-length '(a b c d)) \EV\ 4 \\
(list-length '(a (b c) d)) \EV\ 3 \\
(let ((x (list 'a b c))) \\
~~(rplacd (last x) x) \\
~~(list-length x)) \EV\ {\nil}
\end{lisp}
\cdf{list-length} может быть реализован так:
\begin{lisp}
(defun list-length (x) \\
~~(do ((n 0 (+ n 2))~~~~~~~~~~~~;\textrm{Счётчик} \\
~~~~~~~(fast x (cddr fast))~~~~~;\textrm{Быстрый указатель: на две позиции вперёд} \\
~~~~~~~(slow x (cdr slow)))~~~~~;\textrm{Медленный указатель: на одну позицию} \\
~~~~~~(nil) \\
~~~~;; Если быстрый указатель дошёл до конца, вернуть длину. \\
~~~~(when (endp fast) (return n)) \\
~~~~(when (endp (cdr fast)) (return (+ n 1))) \\
~~~~;; If fast pointer eventually equals slow pointer, \\
~~~~;;  then we must be stuck in a circular list. \\
~~~~;; (A deeper property is the converse: if we are \\
~~~~;;  stuck in a circular list, then eventually the \\
~~~~;;  fast pointer will equal the slow pointer. \\
~~~~;;  That fact justifies this implementation.) \\
~~~~(when (and (eq fast slow) (> n 0)) (return nil))))
\end{lisp}
Смотрите \cdf{length}, которая возвращает длину любой последовательности.
\end{defun}

\begin{defun}[Функция]
nth n list

\cd{(nth \emph{n} \emph{list})} возвращает \emph{n}-нный элемент списка
\emph{list}. \emph{car} элемент списка принимается за <<нулевой>> элемент.
Аргумент \emph{n} должен быть неотрицательным целым числом.
Если длина списка не больше чем \emph{n}, тогда результат {\emptylist}, или
другими словами {\nil}.
(Это согласовывается с концепцией того, что \emph{car} и \emph{cdr} от
{\emptylist} являются {\emptylist}.)
Например:
\begin{lisp}
(nth 0 '(foo bar gack)) \EV\ foo \\
(nth 1 '(foo bar gack)) \EV\ bar \\
(nth 3 '(foo bar gack)) \EV\ {\emptylist}
\end{lisp}

\cdf{nth} может быть использован в связке с \cdf{setf} для изменения элемента
списка. В этом случае, аргумент \emph{n} должен быть меньше чем длина списка
\emph{list}.

Следует отметить, что порядок аргументов в \cdf{nth} обратный в отличие от
большинства других функций селекторов для последовательностей, таких ка
\cdf{elt}.
\end{defun}

\begin{defun}[Функция]
first list \\
second list \\
third list \\
fourth list \\
fifth list \\
sixth list \\
seventh list \\
eighth list \\
ninth list \\
tenth list

Иногда эти функции удобно использовать для доступа к определёнными элементам
списка.
\cdf{first} то же, что и \cdf{car}, \cdf{second} то же, что и \cdf{cadr},
\cdf{third} то же, что и \cdf{caddr}, и так далее.
Следует отметить, что нумерация начинается с единицы (first) в отличие от
нумерации, которая начинается с нуля и используется в \cdf{nth}.
\begin{lisp}
(fifth x) \EQ\ (nth 4 x)
\end{lisp}

Каждая из этих функций может быть использована в связке \cdf{setf} для изменения
элемента массива. 
\end{defun}

\begin{defun}[Функция]
rest list

\cdf{rest} означает то же, что и \cdf{cdr}, но мнемонически согласуется с
\cdf{first}.
\cdf{rest} может использоваться в связке с \cdf{setf} для изменения элементов
массива.
\end{defun}

\begin{defun}[Функция]
nthcdr n list

\cd{(nthcdr \emph{n} \emph{list})} выполняет для
списка \emph{lisp} операцию \cdf{cdr} \emph{n} раз, и возвращает результат.
Например:
\begin{lisp}
(nthcdr 0 '(a b c)) \EV\ (a b c) \\
(nthcdr 2 '(a b c)) \EV\ (c) \\
(nthcdr 4 '(a b c)) \EV\ {\emptylist}
\end{lisp}
Другими словами, она возвращает \emph{n}-нную \emph{cdr} часть списка.

\begin{lisp}
(car (nthcdr n x)) \EQ\ (nth n x)
\end{lisp}
Аргумент \emph{n} должен быть неотрицательным целым числом.
\end{defun}

\begin{defun}[Функция]
last list &optional (n 1)

\cdf{last} возвращает последние \emph{n} cons-ячеек списка \emph{lisp}. Список
\emph{list} может быть списком с точкой. Передача зацикленного списка является
ошибкой.

Аргумент \emph{n} должен быть неотрицательным целым числом.
Если \emph{n} равен нулю, тогда возвращается последний атом списка
\emph{list}. Если \emph{n} не меньше чем количество cons-ячеек, то возвращается
весь список.

Например:
\begin{lisp}
(setq x '(a b c d)) \\
(last x) \EV\ (d) \\
(rplacd (last x) '(e f)) \\
x \EV\ '(a b c d e f) \\
(last x 3) \EV\ (d e f) \\
(last '()) \EV\ () \\
(last '(a b c . d)) \EV\ (c . d) \\
(last '(a b c . d) 0) \EV\ d \\
(last '(a b c . d) 2) \EV\ (b c . d) \\
(last '(a b c . d) 1729) \EV\ (a b c . d)
\end{lisp}
\end{defun}

\begin{defun}[Функция]
list &rest args

\cdf{list} создаёт и возвращает список, составленный из аргументов.
Например:
\begin{lisp}
(list 3 4 'a (car '(b . c)) (+ 6 -2)) \EV\ (3 4 a b 4)
\end{lisp}

\begin{lisp}
(list) \EV\ () \\
(list (list 'a 'b) (list 'c 'd 'e)) \EV\ ((a b) (c d e))
\end{lisp}
\end{defun}

\begin{defun}[Функция]
list* arg &rest others

\cdf{list*} похожа на \cdf{list} за исключением того, что последняя
\emph{cons}-ячейка создаваемого списка будет <<с точкой>>. Последний аргумент
используется как последний элемент списка, а именно в последней cons-ячейки в
\emph{cdr} элементе. Данный аргумент необязательно должен быть атомом, и если он
не атом, то в результате список будет иметь большую длину чем количество
аргументов.
Например:
\begin{lisp}
(list* 'a 'b 'c 'd) \EV\ (a b c . d)
\end{lisp}
Это то же, что и
\begin{lisp}
(cons 'a (cons 'b (cons 'c 'd)))
\end{lisp}
А также:
\begin{lisp}
(list* 'a 'b 'c '(d e f)) \EV\ (a b c d e f) \\*
(list* x) \EQ\ x
\end{lisp}
\end{defun}

\begin{defun}[Функция]
make-list size &key :initial-element

Функция создаёт и возвращает список содержащий количество \emph{size} элементов,
каждый из которых будет инициализирован значением аргумента
\cd{:initial-element} (который по-умолчанию {\false}).
\emph{size} должен быть неотрицательным целым числом.
Например:
\begin{lisp}
(make-list 5) \EV\ ({\false} {\false} {\false} {\false} {\false}) \\
(make-list 3 \cd{:initial-element} 'rah) \EV\ (rah rah rah)
\end{lisp}
\end{defun}

\begin{defun}[Функция]
append &rest lists

Функция возвращает список содержащий все элементы указанных в аргументах списков.
Аргументы не разрушаются.
Например:
\begin{lisp}
(append '(a b c) '(d e f) '{\emptylist} '(g)) \EV\ (a b c d e f g)
\end{lisp}
Следует отметить, что \cdf{append} копирует верхний уровень всех переданных
списков \emph{за исключением} последнего.
Функция \cdf{concatenate} выполняет похожую операцию, но всегда копирует все
аргументы. Смотрите также \cdf{nconc}, которая похожа на \cdf{append}, но
разрушает все аргументы кроме последнего.

Последний аргумент может быть любым Lisp объектом, и в этом случае этот объект
становится последним элементов итогового списка.
Например, \cd{(append '(a b c) 'd)} \EV\ \cd{(a b c . d)}.

\cd{(append \emph{x} '{\emptylist})} может быть использовано для копирования
списка \emph{x}, однако для этого больше подходит функция \cdf{copy-list}.
\end{defun}

\begin{defun}[Функция]
copy-list list

Функция возвращает список, который равен \cdf{equal} и в то же время не равен
\cdf{eq} списку \emph{list}, 
Копируется только верхний уровень списка, то есть \cdf{copy-list} копирует
только в направлении \emph{cdr} элементов, но не в направлении \emph{car}
элементов.
Если список <<с точкой>>, то есть \cd{(cdr (last \emph{list}))} является
не-{\nil} атомом, тогда итоговый список также будет <<с точкой>>.
Смотрите также \cdf{copy-seq} и \cdf{copy-tree}.
\end{defun}

\begin{defun}[Функция]
copy-alist list

\cdf{copy-alist} копирует ассоциативные списки. При этом, также как и в
\cdf{copy-list}, копируется только верхний уровень списка \emph{lisp}.
Кроме того, каждый элемент списка \emph{list}, являющийся в свою очередь
cons-ячейкой, заменяется новой cons-ячейкой с теми же \emph{car} и \emph{cons}
элементами.
\end{defun}

\begin{defun}[Функция]
copy-tree object

\cdf{copy-tree} копирует древовидно организованные cons-ячейки.
Аргумент \emph{object} может быть любым Lisp'овым объектом.
Если он не является cons-ячейкой, то ничего не произойдёт и данный объект будет
возвращён в качестве результата. В противном случае будет возвращена новая
cons-ячейка, в которой \emph{car} и \emph{cons} элементы будут результатами
рекурсивных вызовов \cdf{copy-tree}. Другими словами, все cons-ячейки будут
рекурсивно скопированы, и рекурсия будет останавливаться только на атомах.
\end{defun}

\begin{defun}[Функция]
revappend x y

\cd{(revappend \emph{x} \emph{y})} похожа на \cd{(append (reverse \emph{x})
   \emph{y})} за исключением того, что она потенциально более
 производительна. Аргументы \emph{x} и \emph{y} должны быть списками.
Аргумент \emph{x} копируется (не разрушается) в отличие от \cdf{nreconc},
которая разрушает первый аргумент.
\end{defun}

\begin{defun}[Функция]
nconc &rest lists

В качестве аргументов \cdf{nconc} принимает списки. Функция соединяет списки и
возвращает результат. При этом аргументы изменяются, а не копируются.
(В сравнении с \cdf{append}, которая копирует аргументы, а не разрушает их.)
Например:
\begin{lisp}
(setq x '(a b c)) \\
(setq y '(d e f)) \\
(nconc x y) \EV\ (a b c d e f) \\
x \EV\ (a b c d e f)
\end{lisp}
Следует отметить, что в примере, значение \cdf{x} отличается от первоначального,
так как последняя cons-ячейка была изменена с помощью \cdf{rplacd} значением
\cdf{y}.
Если сейчас выполнить \cd{(nconc x y)} ещё раз, тогда часть списка зациклится:
\cd{(a b c d e f d e f d e f ...)}, и так до бесконечности.
Если \cdf{*print-circle*} не равен {\nil}, тогда вывод списка будет таким:
\cd{(a b c . \#1=(d e f . \#1\#))}.

Вызов \cdf{nconc}, совпадающий
с наиболее близким шаблоном выражения в левой части приводит к эквивалентным
побочным действиям, как в правой части таблицы.
\begin{flushleft}
\begin{tabular}{@{}ll@{}}
\cd{(nconc)}&\cd{nil~~~~~;}\textrm{Нет побочных эффектов} \\
\cd{(nconc nil . \emph{r})~~~~}&\cd{(nconc . \emph{r})} \\
\cd{(nconc \emph{x})}&\emph{x} \\
\cd{(nconc \emph{x} \emph{y})}&\cd{(let ((p \emph{x}) (q \emph{y}))} \\
                                  &\cd{~~(rplacd (last p) q)} \\
                                  &\cd{~~p)} \\
\cd{(nconc \emph{x} \emph{y} . \emph{r})}&\cd{(nconc (nconc \emph{x} \emph{y})
  . \emph{r})}
\end{tabular} 
\end{flushleft}
\end{defun}

\penalty-10000 %manual

\begin{defun}[Функция]
nreconc x y

\cd{(nreconc \emph{x} \emph{y})} похожа на \cd{(nconc (nreverse \emph{x})
  \emph{y})} за исключением того, что она потенциально эффективнее.
Оба аргумента должны быть списками. 
Аргумент \emph{x} разрушается.
Сравните с \cdf{revappend}.

\begin{lisp}
(setq planets '(jupiter mars earth venus mercury)) \\
(setq more-planets '(saturn uranus pluto neptune)) \\
(nreconc more-planets planets) \\
\`\EV\ (neptune pluto uranus saturn jupiter mars earth venus mercury) \\
~~\textrm{теперь значение \cdf{more-planets} точно не определено}
\end{lisp}

Поведение \cd{(nreconc \emph{x} \emph{y})} совпадает с поведением \cd{(nconc
  (nreverse \emph{x})~\emph{y})} в части побочных эффектов.
\end{defun}

\begin{defmac}
push item place

Форма \emph{place} должна быть именем обобщённое переменной, содержащей
список. \emph{item} может указывать на любой Lisp'овый объект. \emph{item}
вставляется в начало списка и данный список возвращается в качестве результата.
Форма \emph{place} может
быть любой формой, которая подходит для \cdf{setf}.
Если рассматривать список как стек, тогда \cdf{push} добавляет элемент на
вершину стека.
Например:
\begin{lisp}
(setq x '(a (b c) d)) \\
(push 5 (cadr x)) \EV\ (5 b c)  \textrm{и теперь} x \EV\ (a (5 b c) d)
\end{lisp}
Действие от
\begin{lisp}
(push \emph{item} \emph{place})
\end{lisp}
эквивалентно действию
\begin{lisp}
(setf \emph{place} (cons \emph{item} \emph{place}))
\end{lisp}
за исключением того, что \cdf{push} выполняет форму \emph{place} только один раз,
а не три.
Более того, в для некоторых форм \emph{place} \cdf{push} может быть
эффективнее чем версия с \cdf{setf}.

Следует отметить, что \emph{item} вычисляется прежде чем вычисляется
\emph{place}.
\end{defmac}

\begin{defmac}
pushnew item place &key :test :test-not :key

Форма \emph{place} должна быть именем обобщённое переменной, содержащей
список. \emph{item} может указывать на любой Lisp'овый объект. Если \emph{item}
не содержится в списке (этот факт устанавливается с помощью предиката
переданного в \cd{:test}, который по-умолчанию \cdf{eql}), тогда \emph{item}
вставляется в начало списка и данный список возвращается в качестве результата.
В противном случае возвращается исходный список. Форма \emph{place} может
быть любой формой, которая подходит для \cdf{setf}.
Если рассматривать список как множество, тогда \cdf{pushnew} добавляет элемент в
множество. Смотрите \cdf{adjoin}.

Именованные параметры \cdf{pushnew} имеют тот же смысл, что и в функциях для
последовательностей. Смотрите главу~\ref{KSEQUE}.
По сути, данные аргументы идентичны аргументам \cdf{adjoin}.

\cdf{pushnew} возвращает модифицированное содержимое переменной \emph{place}.
Например:
\begin{lisp}
(setq x '(a (b c) d)) \\
(pushnew 5 (cadr x)) \EV\ (5 b c)   \textrm{и теперь} x \EV\ (a (5 b c) d) \\
(pushnew 'b (cadr x)) \EV\ (5 b c)  \textrm{и \cdf{x} не меняется}
\end{lisp}
Действие от
\begin{lisp}
(pushnew \emph{item} \emph{place} \cd{:test} \emph{p})
\end{lisp}
эквивалентно действию
\begin{lisp}
(setf \emph{place} (adjoin \emph{item} \emph{place} \cd{:test} \emph{p}))
\end{lisp}
за исключением того, что \cdf{pushnew} выполняет форму \emph{place} только один раз,
а не три.
Более того, в для некоторых форм \emph{place} \cdf{pushnew} может быть
эффективнее чем версия с \cdf{setf}.

Следует отметить, что \emph{item} вычисляется прежде чем вычисляется
\emph{place}.
\end{defmac}

\begin{defmac}
pop place

Форма \emph{place} должна быть именем обобщённое переменной, содержащей
список. Результатом \cdf{pop} является результат \cdf{car} функции для
переданного списка, и побочным эффектом является то, что в обобщённую переменную
сохраняется результат \cdf{cdr} для списка.
Форма \emph{place} может быть любой формой, которая подходит для
\cdf{setf}. Если рассматривать исходный список как стек, то \cdf{pop} достаёт
элемент из вершины стека и возвращает его.
Например:
\begin{lisp}
(setq stack '(a b c)) \\
(pop stack) \EV\ a  \textrm{and now} stack \EV\ (b c)
\end{lisp}
Действия от \cd{(pop \emph{place})} эквивалентно
\begin{lisp}
(prog1 (car \emph{place}) (setf \emph{place} (cdr \emph{place})))
\end{lisp}
за исключением того, что \cdf{pop} выполняет форму \emph{place} только один раз,
а не три.
Более того, в для некоторых форм \emph{place} \cdf{pop} может быть
эффективнее чем версия с \cdf{setf}. 
\end{defmac}

\begin{defun}[Функция]
butlast list &optional n

Функция создаёт и возвращает список с такими же элементами кроме \emph{n}
последних, что и в списке \emph{list}.
\emph{n} по-умолчанию равно 1. Аргумент не разрушается.
Если длина списка \emph{list} меньше чем \emph{n}, тогда возвращается
{\emptylist}.
Например:
\begin{lisp}
(butlast '(a b c d)) \EV\ (a b c) \\
(butlast '((a b) (c d))) \EV\ ((a b)) \\
(butlast '(a)) \EV\ {\emptylist} \\
(butlast nil) \EV\ {\emptylist}
\end{lisp}
Имя функции образовано от фразы <<all elements but the last>> (<<все элементы
кроме последних>>).
\end{defun}

\begin{defun}[Функция]
nbutlast list &optional n

Это деструктивная версия \cdf{butlast}. Данная функция изменяет \emph{cdr}
элемент cons-ячейки на {\nil}. Искомая cons-ячейка находится на позиции
\emph{n}+1 с конца списка. Если длина списка \emph{list} меньше чем \emph{n},
тогда возвращается {\emptylist}, и аргумент не модифицируется. (Таким образом
можно написать \cd{(setq a (nbutlast a))}, а не \cd{(nbutlast a)}.)
Например:
\begin{lisp}
(setq foo '(a b c d)) \\
(nbutlast foo) \EV\ (a b c) \\
foo \EV\ (a b c) \\
(nbutlast '(a)) \EV\ {\emptylist} \\
(nbutlast '{\nil}) \EV\ {\emptylist}
\end{lisp}
\end{defun}

\begin{defun}[Функция]
ldiff list sublist

Аргумент \emph{list} должен быть списком, и \emph{sublist} должен быть
подсписком \emph{list}.
\cdf{ldiff} (означает <<list difference>>) возвращает новый список, элементы
которого содержат все элементы списка \emph{list} до подсписка
\emph{sublist}. Если \emph{sublist} не является частью \emph{list} (или в
частности равен {\nil}), тогда возвращается копия всего списка \emph{list}.
Аргумент \emph{list} не разрушается.
Например:
\begin{lisp}
(setq x '(a b c d e)) \\
(setq y (cdddr x)) \EV\ (d e) \\
(ldiff x y) \EV\ (a b c) \\[4pt]
\textrm{но} (ldiff '(a b c d) '(c d)) \EV\ (a b c d)
\end{lisp}
так как подсписок не равен \cdf{eq} ни одной части списка.
\end{defun}

\section{Изменение структуры списка}

Для изменения структуры уже имеющегося списка могут использоваться функции
\cdf{rplaca} и \cdf{rplacd}. Данные функции изменяют \emph{car} и \emph{cdr}
элементы cons-ячеек соответственно.
Можно также использовать \cdf{setf} в связке с \cdf{car} и \cdf{cdr}.

Структура списка деструктивно изменяется, а не копируется. Такое поведение может
оказаться неожиданным, особенно при использовании частей списком, на которые
указывают более одной переменной.
Описанные ранее функции \cdf{nconc}, \cdf{nreverse}, \cdf{nreconc},
и \cdf{nbutlast} также деструктивно изменяют список.
Данные функции имеют <<копирующие, а не разрушающие>> аналоги.

\begin{defun}[Функция]
rplaca x y

\cd{(rplaca \emph{x} \emph{y})} изменяет \emph{car} элемент в cons-ячейке
\emph{x} на \emph{y} и возвращает (модифицированную) \emph{x}. \emph{x} должен
быть cons-ячейкой, но \emph{y} может быть любым Lisp'овым объектом.
Например:
\begin{lisp}
(setq g '(a b c)) \\
(rplaca (cdr g) 'd) \EV\ (d c) \\
\textrm{Теперь} g \EV\ (a d c)
\end{lisp}
\end{defun}

\begin{defun}[Функция]
rplacd x y

\cd{(rplacd \emph{x} \emph{y})} изменяет \emph{cdr} элемент в cons-ячейке
\emph{x} на \emph{y} и возвращает (модифицированную) \emph{x}. \emph{x} должен
быть cons-ячейкой, но \emph{y} может быть любым Lisp'овым объектом.
Например:
\begin{lisp}
(setq x '(a b c)) \\
(rplacd x 'd) \EV\ (a . d) \\
\textrm{Теперь} x \EV\ (a . d)
\end{lisp}
\end{defun}

Функции \cdf{rplaca} и \cdf{rplacd} пришли из самых ранних версий Lisp'а, как
\cdf{car}, \cdf{cdr} и \cdf{cons}.
Однако, в настоящее время, они, похоже, отходят на второй план.
Все больше и больше Common Lisp программистов используют \cdf{setf} почти
для всех изменений структур: \cd{(rplaca x~y)} становится
\cd{(setf (car x)~y)} или, возможно, \cd{(setf (first x)~y)}.
Ещё более вероятно, что структура \cdf{defstruct} или CLOS класс используют
вместо списком, если структура данных слишком сложная.
В таком случае \cdf{setf} используется в связке с функцией доступа к слоту.

\section{Замещение выражений}

\indexterm{substitution}
Для выполнения операции замещения в древовидной структуре cons-ячеек
предоставлен ряд функций. Все эти функции принимают дерево и описание того, что
на что необходимо заменить. Функции имеют копирующие и деструктивные версии, а
также версии в которых замещение описывается либо двумя аргументами, либо
ассоциативным списком.

Правила именования для этих функций и для их именованных параметров совпадают с
правилами функций для последовательностей. Смотрите раздел~\ref{KSEQUE}.

\begin{defun}[Функция]
subst new old tree &key :test :test-not :key \\
subst-if new test tree &key :key \\
subst-if-not new test tree &key :key

\cd{(subst \emph{new} \emph{old} \emph{tree})} создаёт копию дерева \emph{tree},
замещая элемент \emph{old} элементом \emph{new}. Замещение происходит в любом
месте дерева. Функция возвращает модифицированную копию дерева \emph{tree}.
Исходный объект \emph{tree} не изменяется, но итоговое дерево может иметь
общие с исходным части.

Например:
\begin{lisp}
(subst 'tempest 'hurricane \\
~~~~~~~'(shakespeare wrote (the hurricane))) \\
~~~\EV\ (shakespeare wrote (the tempest)) \\
\\
(subst 'foo '{\nil} '(shakespeare wrote (twelfth night))) \\
~~~\EV\ (shakespeare wrote (twelfth night . foo) . foo) \\
\\
(subst '(a . cons) '(old . pair) \\
~~~~~~~'((old . spice) ((old . shoes) old . pair) (old . pair)) \\
~~~~~~~\cd{:test} \#'equal) \\
~~~\EV\ ((old . spice) ((old . shoes) a . cons) (a . cons))
\end{lisp}
Эта функция не является деструктивной. Она не изменяет \cdf{car} и \cdf{cdr}
элементы уже существующего дерева.
Можно определить \cdf{subst} так:
\begin{lisp}
(defun subst (old new tree \cd{\&rest} x \cd{\&key} test test-not key) \\*
~~(cond ((satisfies-the-test old tree :test test \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~:test-not test-not :key key) \\*
~~~~~~~~~new) \\*
~~~~~~~~((atom tree) tree) \\
~~~~~~~~(t (let ((a (apply \#'subst old new (car tree) x)) \\*
~~~~~~~~~~~~~~~~~(d (apply \#'subst old new (cdr tree) x))) \\
~~~~~~~~~~~~~(if (and (eql a (car tree)) \\*
~~~~~~~~~~~~~~~~~~~~~~(eql d (cdr tree))) \\*
~~~~~~~~~~~~~~~~~tree \\*
~~~~~~~~~~~~~~~~~(cons a d))))))
\end{lisp}
Смотрите также \cdf{substitute}, которая проводит замещение только для верхнего
уровня списка.
\end{defun}

\begin{defun}[Функция]
nsubst new old tree &key :test :test-not :key \\
nsubst-if new test tree &key :key \\
nsubst-if-not new test tree &key :key

\cdf{nsubst} является деструктивным аналогом \cdf{subst}. В дереве \emph{tree}
любой элемент \emph{old} заменяется на \emph{new}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\begin{defun}[Функция]
sublis alist tree &key :test :test-not :key

\cdf{sublis} выполняет замещение объектов в дереве (древовидной структуре из
cons-ячеек).
Первый аргумент \cdf{sublis} является ассоциативным списком.
Второй аргумент --- дерево, в котором выполняется замещение.
\cdf{sublis} проходит по всему дереву включая листья, и если элемент встречается
в качестве ключа в ассоциативном списке, то данный элемент заменяет на значение
ключа.
Данная операция не разрушает дерево. \cdf{sublis} может выполнять несколько
\cdf{subst} операций за один раз.
Например:
\begin{lisp}
(sublis '((x . 100) (z . zprime)) \\*
~~~~~~~~'(plus x (minus g z x p) 4 . x)) \\*
~~~\EV\ (plus 100 (minus g zprime 100 p) 4 . 100) \\*
 \\*
(sublis '(((+ x y) . (- x y)) ((- x y) . (+ x y))) \\*
~~~~~~~~'(* (/ (+ x y) (+ x p)) (- x y)) \\*
~~~~~~~~:test \#'equal) \\*
~~~\EV\ (* (/ (- x y) (+ x p)) (+ x y))
\end{lisp}

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\begin{defun}[Функция]
nsublis alist tree &key :test :test-not :key

\cdf{nsublis} похожа на \cdf{sublis} но деструктивно модифицирует необходимые
элементы дерева \emph{tree}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\section{Использование списков как множеств}

Common Lisp содержит функции, которые позволяют обрабатывать списки элементов
как \emph{множества}.
Сюда входят функции добавления, удаления и поиска элементов в списке,
основанного на различных критериях.
Кроме того, включены функции объединения, пересечения и разности.

Правила наименования данных функций и их именованных параметров в основном
следуют правилам именования функций для последовательностей. Смотрите
главу~\ref{KSEQUE}.

\begin{defun}[Функция]
member item list &key :test :test-not :key \\
member-if predicate list &key :key \\
member-if-not predicate list &key :key

Функция осуществляет поиск элемента, удовлетворяющего условию, в списке
\emph{list}.
Если элемент не найдёт, возвращается {\false}.
Иначе возвращается часть списка, начинающаяся с искомого элемента.
Поиск осуществляется только в верхнем уровне списка.
Эти функции могут использоваться в качестве предикатов.

Например:
\begin{lisp}
(member 'snerd '(a b c d)) \EV\ {\false} \\
(member-if \#'numberp '(a \#{\Xbackslash}Space 5/3 foo)) \EV\ (5/3 foo) \\
(member 'a '(g (a y) c a d e a f)) \EV\ (a d e a f)
\end{lisp}
Следует отметить, что в последнем примере значение, возвращённое \cdf{member},
равно \cdf{eq} части списка, которая начинается на \cdf{a}.
Если \cdf{member} вернула не {\false} значение, то для изменения полученного
элемента списка можно использовать \cdf{rplaca}.

Смотрите также \cdf{find} и \cdf{position}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\begin{defun}[Функция]
tailp sublist list

\cdf{tailp} истинен тогда и только тогда, когда существует такое целое число
\emph{n}, что выполняется
\begin{lisp}
(eql \emph{sublist} (nthcdr \emph{n} \emph{list}))
\end{lisp}
\emph{list} может быть списком с точкой (подразумевается, что реализации могут
использовать \cdf{atom} и не могут \cdf{endp} для проверки конца списка
\emph{list}). FIXME
\end{defun}

\begin{defun}[Функция]
adjoin item list &key :test :test-not :key

\cdf{adjoin} используется для добавления элементов во множество, если этого
элемента во множестве ещё не было. Условие равенства по-умолчанию \cdf{eql}.
\begin{lisp}
(adjoin \emph{item} \emph{list}) \EQ\ (if (member \emph{item} \emph{list}) \emph{list} (cons \emph{item} \emph{list}))
\end{lisp}
Условие равенства может быть любым предикатом. \emph{item} добавляется в список
тогда и только тогда, когда в списке не было ни одного элемента,
<<удовлетворяющего условию>>.

\cdf{adjoin} отклоняется от обычных правил, описанных в главе~\ref{KSEQUE} в
части обработки параметров \emph{item} и \cd{:key}.
Если указана \cd{:key} функция, то она применяется к параметру \emph{item}, также
как и к каждому элементу списка. Обоснование в том, что если \emph{item} ещё не
был в списке и если он там появится, то применение функции \cd{:key} к нему как
элементу списка не будет корректным, если этого не было при его добавлении.
\begin{lisp}
(adjoin \emph{item} \emph{list} :key \emph{fn}) \\
~~\EQ\ (if (member (funcall \emph{fn} \emph{item}) \emph{list}
  :key \emph{fn}) \emph{list} (cons \emph{item} \emph{list})) 
\end{lisp}

Смотрите также \cdf{pushnew}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\begin{defun}[Функция]
union list1 list2 &key :test :test-not :key \\
nunion list1 list2 &key :test :test-not :key

\cdf{union} принимает два списка и возвращает новый список, содержащий всё, что
является элементами списков \emph{list1} и \emph{list2}.
Если в списках есть дубликаты, то в итоговом будет только один экземпляр.
Например:
\begin{lisp}
(union '(a b c) '(f a d)) \\
~~~\EV\ (a b c f d) \textrm{или} (b c f a d) \textrm{или} (d f a b c) \textrm{или} ... \\
 \\
(union '((x 5) (y 6)) '((z 2) (x 4)) :key \#'car) \\
~~~\EV\ ((x 5) (y 6) (z 2)) \textrm{или} ((x 4) (y 6) (z 2)) \textrm{или} ...
\end{lisp}

Порядок элементов в итоговом списке не обязательно совпадает с порядком
соответствующих элементов в списках.
Итоговый список может иметь общие ячейки с или быть равным \cdf{eq} переданным
аргументам.

Функция \cd{:test} может быть любым предикатом, и операция объединения может
быть описана следующим образом. Для всех возможных упорядоченных пар, состоящих
из одного элемента из списка \emph{list1} и одного элемента из списка
\emph{list2}, предикат устанавливает <<равны>> ли они. Для каждой пары равных
элементов, как минимум один из двух элементов будет помещён в результат. Кроме
того, любой элемент, которые не был равен ни одному другому элементу, также
будет помещён в результат. Это описание может быть полезным при использовании
хитрых функций проверки равенства.

Аргумент \cd{:test-not} может быть полезен, когда функция проверки равенства
является логическим отрицанием проверки равенства. Хороший пример такой функции
это \cdf{mismatch}, которая логически инвертирована так, что если аргументы не
равны, то может быть получена возможная полезная информация. Эта дополнительная
<<полезная информация>> отбрасывается в следующем примере. \cdf{mismatch}
используется только как предикат.
\begin{lisp}
(union '(\#(a b) \#(5 0 6) \#(f 3)) \\
~~~~~~~'(\#(5 0 6) (a b) \#(g h)) \\
~~~~~~~:test-not \\
~~~~~~~\#'mismatch) \\
~~~\EV\ (\#(a b) \#(5 0 6) \#(f 3) \#(g h))~~~~~;\textrm{Возможный результат} \\
~~~\EV\ ((a b) \#(f 3) \#(5 0 6) \#(g h))~~~~~~;\textrm{Другой возможный результат}
\end{lisp}
Использование \cd{\cd{:test-not} \#'mismatch} отличается от использования
\cd{\cd{:test} \#'equalp}, например, потому что \cdf{mismatch} определяет что
\cd{\#(a b)} и \cd{(a b)} одинаковы, тогда как \cdf{equalp} определяет эти
выражения разными.

\cdf{nunion} является деструктивной версией \cdf{union}.
Она выполняет ту же операцию, но может разрушить аргументы, возможно при
использовании их ячеек для построения результата.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations;
\cdf{nunion} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of 
any of the argument lists.
\end{newer}
\end{defun}

\begin{defun}[Функция]
intersection list1 list2 &key :test :test-not :key \\
nintersection list1 list2 &key :test :test-not :key

\cdf{intersection} принимает два списка и возвращает новый список содержащий все
элементы, которые есть и в первом и во втором списках одновременно.
Например:
\begin{lisp}
(intersection '(a b c) '(f a d)) \EV\ (a)
\end{lisp}

Порядок элементов в итоговом списке не обязательно совпадает с порядком
соответствующих элементов в списках.
Итоговый список может иметь общие ячейки с или быть равным \cdf{eq} переданным
аргументам.

Функция \cd{:test} может быть любым предикатом, и операция пересечения может
быть описана следующим образом. Для всех возможных упорядоченных пар, состоящих
из одного элемента из списка \emph{list1} и одного элемента из списка
\emph{list2}, предикат устанавливает <<равны>> ли они. Для каждой пары равных
элементов, только один из двух элементов будет помещён в результат. Больше
никаких элементов в итоговом списке не будет. Это описание может быть полезным
при использовании хитрых функций проверки равенства.

\cdf{nintersection} является является деструктивной версией \cdf{intersection}.
Она выполняет ту же операцию, но может разрушить аргумент \emph{list1}, возможно при
использовании их ячеек для построения результата. (Аргумент \emph{list2} не
разрушается.)

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations;
\cdf{nintersection} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of 
any of the argument lists.
\end{newer}
\end{defun}

\begin{defun}[Функция]
set-difference list1 list2 &key :test :test-not :key \\
nset-difference list1 list2 &key :test :test-not :key

\cdf{set-difference} возвращает список элементов списка \emph{list1}, которые не
встречаются в списке \emph{list2}. Данная операция не разрушает аргументы.

Порядок элементов в итоговом списке не обязательно совпадает с порядком
соответствующих элементов в списке \emph{list1}.
Итоговый список может иметь общие ячейки, или быть равным \cdf{eq} аргументу
\emph{list1}.

\emph{:test} может быть любым предикатом, и операция разности множеств может
быть описана следующим образом. Для всех возможных упорядоченных пар,
состоящих из элементов первого и второго списков, используется предикат для
установки их <<равенства>>. Элемент из списка \emph{list1} помещается в
результат, тогда и только тогда, когда он не равен ни одному элементу списка. Это
позволяет делать очень интересные приложения.
Например, можно удалить из списка строк все строки, содержащие некоторый список символов:
\emph{list2}.
\begin{lisp}
;; Удалить все имена специй содержащие буквы "c" или "w". \\
(set-difference '("strawberry" "chocolate" "banana" \\
~~~~~~~~~~~~~~~~~~"lemon" "pistachio" "rhubarb") \\
~~~~~~~~~~~~~~~~'(\#{\Xbackslash}c \#{\Xbackslash}w) \\
~~~~~~~~~~~~~~~~:test \\
~~~~~~~~~~~~~~~~\#'(lambda (s c) (find c s))) \\
~~~\EV\ ("banana" "rhubarb" "lemon")~~~~~;\textrm{Возможен другой порядок
  элементов}
\end{lisp}

\cdf{nset-difference} является деструктивной версией
\cdf{set-difference}. Данная операция может разрушить \emph{list1}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\begin{defun}[Функция]
set-exclusive-or list1 list2 &key :test :test-not :key \\
nset-exclusive-or list1 list2 &key :test :test-not :key

\cdf{set-exclusive-or} возвращает список элементов, которые встречаются только в
списке \emph{list1} и только в списке \emph{list2}.
Данная операция не разрушает аргументы.

Порядок элементов в итоговом списке не обязательно совпадает с порядком
соответствующих элементов в списке \emph{list1}.
Итоговый список может иметь общие ячейки, или быть равным \cdf{eq} аргументу
\emph{list1}.

Функция проверки равенства элементов может быть любым предикатом, и операцию
\cdf{set-exclusive-or} можно описать следующим образом. Для всех возможных
упорядоченных пар, содержащих один элемент из списка \emph{list1} и один элемент
из списка \emph{list2}, функция используется для проверки
<<равенства>>. Результат содержит точно те элементы списков \emph{list1} и
\emph{list2}, которые были только в различающихся парах.

\cdf{nset-exclusive-or} является деструктивной версией
\cdf{set-exclusive-or}. Данная операция может разрушить аргументы.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations;
\cdf{nset-exclusive-or} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of 
any of the argument lists.
\end{newer}
\end{defun}

\begin{defun}[Функция]
subsetp list1 list2 &key :test :test-not :key

\cdf{subsetp} является предикатом, который истинен, если каждый элемент списка
\emph{list1} встречается в (<<равен>> некоторому элементу в) списке
\emph{list2}, иначе ложен.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\section{Ассоциативные списки}

\emph{Ассоциативный список}, или \emph{a-list}, является структурой данных,
часто используемой в Lisp'е. a-list является списком пар (cons-ячеек). Каждая
пара является ассоциацией. \emph{car} элемент пары называется \emph{key}, и
\emph{cdr} элемент \emph{datum}.

Преимущество a-list представления данных в том, что a-list может быть
постепенно увеличен путём простого добавления в начало новых записей.
Кроме того, поскольку функция поиска \cdf{assoc} по порядку проходит элементы
a-list, то новые записи могут <<скрыть>> старые. Если a-list
рассматривать как отображение ключей в значения, то отображение может быть не
только увеличено, но также изменено с помощью добавления новых записей в начало
a-list.

Иногда a-list представляет биективное (bijective) отображение, и бывает нужно
получить ключ для некоторого значения. Для этих целей используется функция
<<реверсивного>> поиска \cdf{rassoc}. Другие варианты поиска в a-list могут быть
созданы с помощью функции \cdf{find} или \cdf{member}.

Допустимо, чтобы {\false} был элемент a-list вместо пары ключ-значение.
Такой элемент не считается парой и просто пропускается при использовании
функции \cdf{assoc}.

\begin{defun}[Функция]
acons key datum a-list

\cdf{acons} создаёт новый ассоциативный список, с помощью добавления пары
\cd{(\emph{key} . \emph{datum})} к старому \emph{a-list}.
\begin{lisp}
(acons x y a) \EQ\ (cons (cons x y) a)
\end{lisp}
\end{defun}

\begin{defun}[Функция]
pairlis keys data &optional a-list

\cdf{pairlis} принимает два списка и создаёт ассоциативный список, который
связывает элементы первого списка с соответствующими элементами второго. Если
списки не одинаковой длины, это является ошибкой. Если указан необязательный
аргумент \emph{a-list}, тогда новые пары добавляются к нему в начало.

Новые пары могут быть расположены в итоговом списке a-list в любом порядке.
Например:
\begin{lisp}
(pairlis '(one two) '(1 2) '((three . 3) (four . 19)))
\end{lisp}
может быть
\begin{lisp}
((one . 1) (two . 2) (three . 3) (four . 19))
\end{lisp}
или может быть так
\begin{lisp}
((two . 2) (one . 1) (three . 3) (four . 19))
\end{lisp}
\end{defun}

\begin{defun}[Функция]
assoc item a-list &key :test :test-not :key \\
assoc-if predicate a-list &key :key \\
assoc-if-not predicate a-list &key :key

Каждая из этих функций осуществляет поиск в ассоциативном списке
\emph{a-list}. Функция возвращает первую пару, удовлетворяющую условию, или
{\false}, если такой пары не было найдено.
Например:
\begin{lisp}
(assoc 'r '((a . b) (c . d) (r . x) (s . y) (r . z))) \\
~~~~~~~~\EV\  (r . x) \\
(assoc 'goo '((foo . bar) (zoo . goo))) \EV\ {\false} \\
(assoc '2 '((1 a b c) (2 b c d) (-7 x y z))) \EV\ (2 b c d)
\end{lisp}
Если функция вернула пару, можно изменить её значение с помощью \cdf{rplacd}.
(Однако лучше будет добавить новую <<затеняющую>> пару в начало, чем
модифицировать старую.)
Например:
\begin{lisp}
(setq values '((x . 100) (y . 200) (z . 50))) \\
(assoc 'y values) \EV\ (y . 200) \\
(rplacd (assoc 'y values) 201) \\
(assoc 'y values) \EV\ (y . 201) \textrm{теперь}
\end{lisp}
Типичный приём использования \cd{(cdr (assoc x y))}.
Так как \emph{cdr} от {\false} гарантировано вычисляется в {\false}, то в случае
отсутствия нужной пары, будет возвращено значение {\false}. {\false} также
будет возвращено, если значение для ключа равно {\false}. Такое поведение
удобно, если {\false} несёт смысл <<значения по-умолчанию>>.

Два выражения
\begin{lisp}
(assoc \emph{item} \emph{list} :test \emph{fn})
\end{lisp}
и 
\begin{lisp}
(find \emph{item} \emph{list} :test \emph{fn} :key \#'car)
\end{lisp}
эквивалентны за исключением, того что \cdf{assoc} игнорирует значения {\nil} на
месте пар.

Смотрите также \cdf{find} и \cdf{position}.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\begin{defun}[Функция]
rassoc item a-list &key :test :test-not :key \\
rassoc-if predicate a-list &key :key \\
rassoc-if-not predicate a-list &key :key

\cdf{rassoc} является реверсивной формой для \cdf{assoc}. Функция ищет пары, у
которых \emph{cdr} элемент удовлетворяет заданному условию.
Если \emph{a-list} рассматривается как отображение, то \cdf{rassoc} обрабатывает
\emph{a-list} как представление инверсного отображения.
Например:
\begin{lisp}
(rassoc 'a '((a . b) (b . c) (c . a) (z . a))) \EV\ (c . a)
\end{lisp}

Выражения 
\begin{lisp}
(rassoc \emph{item} \emph{list} :test \emph{fn})
\end{lisp}
и
\begin{lisp}
(find \emph{item} \emph{list} :test \emph{fn} :key \#'cdr)
\end{lisp}
эквивалентны за исключением, того что \cdf{rassoc} игнорирует значения {\nil} на
месте пар.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}

Пользователь ограничен в создании побочных действий так, как это описано в
разделе~\ref{STRUCTURE-TRAVERSAL-SECTION}
\end{defun}

\fi