kseque.tex

%Part{KSeque, 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{Sequences}
\label{KSEQUE}

The type \cdf{sequence} encompasses both lists and vectors (one-dimensional
arrays).
While these are different data structures with different structural
properties leading to different algorithmic uses, they do have a common
property: each contains an ordered set of elements.
Note that {\nil} is considered to be a sequence of length zero.

Some operations are useful on both lists and arrays
because they deal with ordered sets of elements.  One may ask the number
of elements, reverse the ordering, extract a subsequence, and so on.  For
such purposes Common Lisp provides a set of generic functions on sequences.

Note that this remark, predating the design of the Common Lisp Object System,
uses the term ``generic'' in a generic sense, and not necessarily
in the technical sense used by CLOS
(see chapter~\ref{DTYPES}).

\begin{flushleft}
\cf
\begin{tabular*}{\textwidth}{@{}l@{\extracolsep{\fill}}lll@{}}
\cdf{elt}&\cdf{reverse}&\cdf{map}&\cdf{remove} \\
\cdf{length}&\cdf{nreverse}&\cdf{some}&\cdf{remove-duplicates} \\
\cdf{subseq}&\cdf{concatenate}&\cdf{every}&\cdf{delete} \\
\cdf{copy-seq}&\cdf{position}&\cdf{notany}&\cdf{delete-duplicates} \\
\cdf{fill}&\cdf{find}&\cdf{notevery}&\cdf{substitute} \\
\cdf{replace}&\cdf{sort}&\cdf{reduce}&\cdf{nsubstitute} \\
\cdf{count}&\cdf{merge}&\cdf{search}&\cdf{mismatch}
\end{tabular*}
\end{flushleft}
Some of these operations come in more than one version.
Such versions are indicated by adding a suffix (or occasionally a prefix)
to the basic name of the operation.
In addition, many operations accept one or more optional keyword
arguments that can modify the operation in various ways.

If the operation requires testing sequence elements according to
some criterion, then the criterion may be specified in one of two ways.
The basic operation accepts an item,
and elements are tested for being \cdf{eql} to that item.
(A test other than \cdf{eql} can be specified by the \cd{:test}
or \cd{:test-not} keyword.  It is an error to use both
of these keywords in the same call.)
The variants formed by adding \cdf{-if} and \cdf{-if-not}
to the basic operation name do not take an item,
but instead a one-argument predicate,
and elements are tested for satisfying or not satisfying the predicate.
As an example,
\begin{lisp}
(remove \emph{item} \emph{sequence})
\end{lisp}
returns a copy of \emph{sequence} from which all elements \cdf{eql} to \emph{item}
have been removed;
\begin{lisp}
(remove \emph{item} \emph{sequence} \cd{:test} \#'equal)
\end{lisp}
returns a copy of \emph{sequence} from which all elements \cdf{equal} to \emph{item}
have been removed;
\begin{lisp}
(remove-if \#'numberp \emph{sequence})
\end{lisp}
returns a copy of \emph{sequence} from which all numbers have been removed.

If an operation tests elements of a sequence in any manner,
the keyword argument \cd{:key}, if not {\false}, should be a function
of one argument that will extract from an element the part to be tested
in place of the whole element.
For example, the effect of the MacLisp expression
\cd{(assq item seq)} could be obtained by
\begin{lisp}
(find \emph{item} \emph{sequence} \cd{:test} \#'eq \cd{:key} \#'car)
\end{lisp}
This searches for the first element of \emph{sequence} whose \emph{car} is \cdf{eq}
to \emph{item}.
\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to allow the \cd{:key} function
to be only of type \cdf{symbol} or \cdf{function}; a lambda-expression
is no longer acceptable as a functional argument.  One must use the
\cdf{function} special operator or the abbreviation \cd{\#'} before
a lambda-expression that appears as an  explicit argument form.
\end{newer}

For some operations it can be useful to specify the direction
in which the sequence is conceptually processed.  In this case the basic
operation normally processes the sequence in the forward direction,
and processing in the reverse direction is indicated by a non-{\false}
value for the keyword argument \cd{:from-end}.  (The processing order
specified by the \cd{:from-end} is purely conceptual.  Depending on
the object to be processed and on the implementation, the actual processing
order may be different.  For this reason a user-supplied \emph{test} function
should be free of side effects.)

Many operations allow the specification of a subsequence to be operated
upon.  Such operations have keyword arguments
called \cd{:start} and \cd{:end}.  These arguments should be integer indices
into the sequence, with $\emph{start}\leq\emph{end}$
(it is an error if $\emph{start}>\emph{end}$).  They indicate
the subsequence starting with and \emph{including} element \emph{start}
and up to but \emph{excluding} element \emph{end}.  The length of the subsequence
is therefore $\emph{end}-\emph{start}$.  If \emph{start} is omitted,
it defaults to zero; and if \emph{end} is omitted or {\false}, it defaults to
the length of the sequence.
Therefore if both \emph{start} and \emph{end} are omitted, the entire sequence
is processed by default.
For the most part, subsequence specification
is permitted purely for the sake of efficiency;
one could simply call \cdf{subseq} instead to extract the subsequence
before operating on it.  Note, however, that operations that
calculate indices
return indices into the original sequence, not into the subsequence:
\begin{lisp}
(position \#{\Xbackslash}b "foobar" \cd{:start} 2 \cd{:end} 5) \EV\ 3 \\
(position \#{\Xbackslash}b (subseq "foobar" 2 5)) \EV\ 1
\end{lisp}
If two sequences are involved, then
the keyword arguments
\cd{:start1}, \cd{:end1}, \cd{:start2}, and \cd{:end2} are used to
specify separate subsequences for each sequence.

\begin{newer}
X3J13 voted in June 1988 \issue{SUBSEQ-OUT-OF-BOUNDS}
(and further clarification was voted in January 1989
\issue{RANGE-OF-START-AND-END-PARAMETERS})
to specify that these rules apply not
only to all built-in functions that have keyword parameters named
\cd{:start}, \cd{:start1}, \cd{:start2}, \cd{:end}, \cd{:end1},
or \cd{:end2} but also to functions such as \cdf{subseq}
that take required or optional parameters that are documented
as being named \emph{start} or \emph{end}.
\begin{itemize}
\item A ``start'' argument must always be a non-negative integer and
defaults to zero if not supplied; it is not permissible to pass \cdf{nil}
as a ``start'' argument.
\item An ``end'' argument must be either a
non-negative integer or \cdf{nil} (which indicates the end of the
sequence) and defaults to \cdf{nil}
if not supplied; therefore supplying \cdf{nil} is equivalent to
not supplying such an argument.
\item If the ``end'' argument is an integer, it must be no greater than the
active length of the corresponding sequence
(as returned by the function \cdf{length}).
\item The default value for the ``end'' argument is the active length
of the corresponding sequence.
\item The ``start'' value (after defaulting, if necessary) must not be greater than the
corresponding ``end'' value (after defaulting, if necessary).
\end{itemize}
This may be summarized as follows.
Let \emph{x} be the sequence within which indices are to be considered.  Let \emph{s} be
the ``start'' argument for that sequence of any standard function,
whether explicitly specified or defaulted, through omission, to
zero.  Let \emph{e} be the ``end'' argument for that sequence
of any standard function, whether explicitly specified or defaulted, through
omission or an explicitly passed \cdf{nil} value, to the active length of \emph{x}, as
returned by \cdf{length}.  Then it is an error if the test
\cd{(<=~0~\emph{s}~\emph{e}~(length \emph{x}))}
is not true.
\end{newer}

For some functions, notably \cdf{remove} and \cdf{delete}, the keyword argument
\cd{:count} is used to specify how many occurrences of the item should
be affected.  If this is {\false} or is not supplied, all matching items are
affected.

In the following function descriptions, an element \emph{x} of a sequence
``satisfies the test'' if any of the following holds:
\begin{itemize}
\item
A basic function was called,
\emph{testfn} was specified by the keyword \cd{:test}, and
\cd{(funcall \emph{testfn} \emph{item} (\emph{keyfn} \emph{x}))} is true.

\item
A basic function was called,
\emph{testfn} was specified by the keyword \cd{:test-not}, and
\cd{(funcall \emph{testfn} \emph{item} (\emph{keyfn} \emph{x}))} is false.

\item
An \cdf{-if} function was called, and
\cd{(funcall \emph{predicate} (\emph{keyfn} \emph{x}))} is true.

\item
An \cdf{-if-not} function was called, and
\cd{(funcall \emph{predicate} (\emph{keyfn} \emph{x}))} is false.
\end{itemize}
In each case \emph{keyfn} is the
value of the \cd{:key} keyword argument (the default being the identity
function).  See, for example, \cdf{remove}.

In the following function descriptions,
two elements \emph{x} and \emph{y} taken from sequences ``match'' if
either of the following holds:
\begin{itemize}
\item
\emph{testfn} was specified by the keyword \cd{:test}, and
\cd{(funcall \emph{testfn} (\emph{keyfn} \emph{x}) (\emph{keyfn} \emph{y}))} is true.

\item
\emph{testfn} was specified by the keyword \cd{:test-not}, and
\cd{(funcall \emph{testfn} (\emph{keyfn} \emph{x}) (\emph{keyfn} \emph{y}))} is false.
\end{itemize}
See, for example, \cdf{search}.

\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to allow the \emph{testfn}
or \cdf{predicate}
to be only of type \cdf{symbol} or \cdf{function}; a lambda-expression
is no longer acceptable as a functional argument.  One must use the
\cdf{function} special operator or the abbreviation \cd{\#'} before
a lambda-expression that appears as an  explicit argument form.
\end{newer}

You may depend on the order in which arguments
are given to \emph{testfn}; this permits the use of non-commutative
test functions in a predictable manner.
The order of the arguments to \emph{testfn} corresponds
to the order in which those arguments (or the sequences containing
those arguments)
were given to the sequence function in question.
If a sequence function gives two elements from the same
sequence argument to \emph{testfn}, they are given in the same order in
which they appear in the sequence.

Whenever a sequence function must construct and return
a new vector, it always returns a \emph{simple}
vector (see section~\ref{ARRAY-TYPE-SECTION}).
Similarly, any strings constructed will be simple strings.

\begin{defun}[Function]
complement fn

Returns a function whose value is the same as that of \cdf{not}
applied to the result of applying the function \emph{fn} to the same
arguments.  One could define \cdf{complement} as follows:
\begin{lisp}
(defun complement (fn) \\*
~~\#'(lambda (\&rest arguments) \\*
~~~~~~(not (apply fn arguments))))
\end{lisp}

One intended use of \cdf{complement} is to supplant the use of
\cd{:test-not} arguments and \cdf{-if-not} functions.
\begin{lisp}
(remove-if-not \#'virtuous senators) {\EQ} \\*
~~~(remove-if (complement \#'virtuous) senators) \\
\\
(remove-duplicates telephone-book \\*
~~~~~~~~~~~~~~~~~~~:test-not \#'mismatch) {\EQ} \\*
~~~(remove-duplicates telephone-book \\*
~~~~~~~~~~~~~~~~~~~~~~:test (complement \#'mismatch))
\end{lisp}
\end{defun}

\section{Simple Sequence Functions}

Most of the following functions perform simple operations on a single
sequence; \cdf{make-sequence} constructs a new sequence.

\begin{defun}[Function]
elt sequence index

This returns the element of \emph{sequence} specified by \emph{index},
which must be a non-negative integer less than the length of the \emph{sequence}
as returned by \cdf{length}.
The first element of a sequence has index \cd{0}.

(Note that \cdf{elt} observes the fill pointer in those vectors that have
fill pointers.  The array-specific function \cdf{aref} may be used
to access vector elements that are beyond the vector's fill pointer.)

\cdf{setf} may be used with \cdf{elt} to destructively replace
a sequence element with a new value.
\end{defun}

\begin{defun}[Function]
subseq sequence start &optional end

This returns the subsequence of \emph{sequence} specified by \emph{start} and
\emph{end}.
\cdf{subseq} \emph{always} allocates a new sequence for a result; it never
shares storage with an old sequence.  The result subsequence is always of
the same type as the argument \emph{sequence}.

\cdf{setf} may be used with \cdf{subseq} to destructively replace
a subsequence with a sequence of new values; see also \cdf{replace}.
\end{defun}

\begin{defun}[Function]
copy-seq sequence

A copy is made of the argument \emph{sequence}; the result is \cdf{equalp}
to the argument but not \cdf{eq} to it.
\begin{lisp}
(copy-seq \emph{x}) \EQ\ (subseq \emph{x} 0)
\end{lisp}
but the name \cdf{copy-seq} is more perspicuous when applicable.
\end{defun}

\begin{defun}[Function]
length sequence

The number of elements in \emph{sequence} is returned as a non-negative integer.
If the sequence is a vector with a fill pointer,
the ``active length'' as specified by the fill pointer is returned
(see section~\ref{FILL-POINTER}).
\end{defun}

\begin{defun}[Function]
reverse sequence

The result is a new sequence of the same kind as \emph{sequence},
containing the same elements but in reverse order.
The argument is not modified.
\end{defun}

\begin{defun}[Function]
nreverse sequence

The result is a sequence containing the same elements as \emph{sequence}
but in reverse order.  The argument may be destroyed and re-used to
produce the result.  The result may or may not be \cdf{eq} to the
argument, so it is usually wise to say something like
\cd{(setq x (nreverse x))}, because simply \cd{(nreverse x)} is not
guaranteed to leave a reversed value in \cdf{x}.
\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations.
When the \emph{sequence} is a list,
\cdf{nreverse} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of that list.
When the \emph{sequence} is an array,
\cdf{nreverse} is permitted to re-order the elements of the given array
in order to produce the resulting array.
\end{newer}
\end{defun}

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

This returns a sequence of type \emph{type} and of length \emph{size}, each of
whose elements
has been initialized to the \cd{:initial-element} argument.
If specified, the \cd{:initial-element} argument must be an object that
can be an element of a sequence of type \emph{type}.
For example:
\begin{lisp}
(make-sequence '(vector double-float) \\*
~~~~~~~~~~~~~~~100 \\*
~~~~~~~~~~~~~~~:initial-element 1d0)
\end{lisp}
If an \cd{:initial-element} argument is not specified, then the sequence will
be initialized in an implementation-dependent way.

\begin{new}
X3J13 voted in January 1989
\issue{ARGUMENTS-UNDERSPECIFIED}
to clarify that the \emph{type} argument
must be a type specifier, and the \emph{size} argument
must be a non-negative integer less than the value of
\cdf{array-dimension-limit}.
\end{new}

\begin{newer}
X3J13 voted in June 1989 \issue{SEQUENCE-TYPE-LENGTH} to specify that
\cdf{make-sequence} should signal an error if the sequence \emph{type} specifies the
number of elements and the \emph{size} argument is different.
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{CHARACTER-PROPOSAL}
to specify that if \emph{type} is \cdf{string}, the result is the same
as if \cdf{make-string} had been called with the same \emph{size}
and \cd{:initial-element} arguments.
\end{newer}
\end{defun}

\section{Concatenating, Mapping, and Reducing Sequences}

The functions in this section each operate on an arbitrary number of
sequences except for \cdf{reduce}, which is included here because
of its conceptual relationship to the mapping functions.

\begin{defun}[Function]
concatenate result-type &rest sequences

The result is a new sequence that contains all the elements of all the
sequences in order.  All of the sequences are copied from; the result
does not share any structure with any of the argument sequences (in this
\cdf{concatenate} differs from \cdf{append}).  The type of the result is
specified by \emph{result-type}, which must be a subtype of \cdf{sequence},
as for the function \cdf{coerce}.
It must be possible for every element of the argument sequences to be an
element of a sequence of type \emph{result-type}.

If only one \emph{sequence} argument is provided
and it has the type specified by \emph{result-type},
\cdf{concatenate} is required to copy the argument rather than simply
returning it.  If a copy is not required, but only possibly type conversion,
then the \cdf{coerce} function may be appropriate.

\begin{newer}
X3J13 voted in June 1989 \issue{SEQUENCE-TYPE-LENGTH} to specify that
\cdf{concatenate} should signal an error if the sequence type specifies the
number of elements and the sum of the argument lengths is different.
\end{newer}
\end{defun}

\begin{defun}[Function]
map result-type function sequence &rest more-sequences

The \emph{function} must take as many arguments as there are sequences
provided; at least one sequence must be provided.
The result of \cdf{map} is a sequence such that element \emph{j} is the result
of applying \emph{function} to element \emph{j} of each of the argument
sequences.  The result sequence is as long as the shortest of the
input sequences.

If the \emph{function} has side effects, it can count on being called
first on all the elements numbered \cd{0}, then on all those
numbered \cd{1}, and so on.

The type of the result sequence is specified by the argument \emph{result-type}
(which must be a subtype of the type \cdf{sequence}),
as for the function \cdf{coerce}.
In addition, one may specify {\nil} for the result type, meaning that no
result sequence is to be produced; in this case the \emph{function} is invoked
only for effect, and \cdf{map} returns {\nil}.  This gives an effect similar
to that of \cdf{mapc}.

\begin{newer}
X3J13 voted in June 1989 \issue{SEQUENCE-TYPE-LENGTH} to specify that
\cdf{map} should signal an error if the sequence type specifies the number of
elements and the minimum of the argument lengths is different.
\end{newer}

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

\noindent
For example:
\begin{lisp}
(map 'list \#'- '(1 2 3 4)) \EV\ (-1 -2 -3 -4) \\
(map 'string \\
~~~~~\#'(lambda (x) (if (oddp x) \#{\Xbackslash}1 \#{\Xbackslash}0)) \\
~~~~~'(1 2 3 4)) \\
~~~\EV\ "1010"
\end{lisp}
\end{defun}


\begin{defun}[Function]
map-into result-sequence function &rest sequences

Function \cdf{map-into} destructively modifies the \emph{result-sequence} to
contain the results of applying \emph{function} to corresponding elements of
the argument \emph{sequences} in turn; it then
returns \emph{result-sequence}.

The arguments \emph{result-sequence}
and each element of \emph{sequences} can each be
either a list or a vector (one-dimensional array).
The \emph{function} must accept at least as many arguments as the
number of argument \emph{sequences} supplied to \cdf{map-into}.
If \emph{result-sequence} and
the other argument \emph{sequences} are not all the same length, the iteration
terminates when the shortest sequence is exhausted.  If \emph{result-sequence}
is a vector with a fill pointer, the fill pointer is ignored when
deciding how many iterations to perform, and afterwards the
fill pointer is set to the number of times the \emph{function} was applied.

If the \emph{function} has side effects, it can count on being called
first on all the elements numbered \cd{0}, then on all those
numbered \cd{1}, and so on.

If \emph{result-sequence} is longer than the shortest element of \emph{sequences},
extra elements at the end of \emph{result-sequence} are unchanged.

The function \cdf{map-into} differs from \cdf{map} in that it modifies
an existing sequence rather than creating a new one.  In addition,
\cdf{map-into} can be called with only two arguments (\emph{result-sequence}
and \emph{function}), while \cdf{map} requires at least three arguments.

If \emph{result-sequence} is \cdf{nil}, \cdf{map-into} immediately returns
\cdf{nil}, because \cdf{nil} is a sequence of length zero.
\end{defun}


\begin{defun}[Function]
some predicate sequence &rest more-sequences \\
every predicate sequence &rest more-sequences \\
notany predicate sequence &rest more-sequences \\
notevery predicate sequence &rest more-sequences

These are all predicates.
The \emph{predicate} must take as many arguments as there are sequences
provided.  The \emph{predicate} is first applied to the elements
with index \cd{0} in each of the sequences, and possibly then to
the elements with index \cd{1}, and so on, until a termination
criterion is met or the end of the shortest of the \emph{sequences} is reached.

If the \emph{predicate} has side effects, it can count on being called
first on all the elements numbered \cd{0}, then on all those
numbered \cd{1}, and so on.

\cdf{some} returns as soon as any invocation of \emph{predicate}
returns a non-{\false} value; \cdf{some} returns that value.
If the end of a sequence is reached, \cdf{some} returns {\false}.
Thus, considered as a predicate, it is true if \emph{some} invocation of
\emph{predicate} is true.

\cdf{every} returns {\false} as soon as any invocation of \emph{predicate}
returns {\false}.
If the end of a sequence is reached, \cdf{every} returns a non-{\false} value.
Thus, considered as a predicate, it is true if \emph{every} invocation of
\emph{predicate} is true.

\cdf{notany} returns {\false} as soon as any invocation of \emph{predicate}
returns a non-{\false} value.
If the end of a sequence is reached, \cdf{notany} returns a non-{\false} value.
Thus, considered as a predicate, it is true if \emph{no} invocation of
\emph{predicate} is true.

\cdf{notevery} returns a non-{\false} value as soon as any invocation
of \emph{predicate} returns {\false}.  If the end of a sequence is reached,
\cdf{notevery} returns
{\false}.  Thus, considered as a predicate, it is true if \emph{not every} invocation of
\emph{predicate} is true.

\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]
reduce function sequence &key :from-end :start :end :initial-value

The \cdf{reduce} function combines all the elements of a sequence using
a binary operation; for example, using \cdf{+} one can add up all the
elements.

The specified subsequence of the \emph{sequence} is combined
or ``reduced'' using the
\emph{function}, which must accept two arguments.  The reduction is
left-associative, unless the \cd{:from-end} argument is true (it defaults
to {\nil}), in which case it is right-associative.  If an
\cd{:initial-value} argument is given, it is logically placed before the
subsequence (after it if \cd{:from-end} is true) and included in the
reduction operation.

If the specified subsequence contains exactly one element
and the keyword argument \cd{:initial-value}
is not given, then that element
is returned and the \emph{function} is not called.
If the specified subsequence is empty and an \cd{:initial-value} is given,
then the \cd{:initial-value} is returned
and the \emph{function} is not called.

If the specified subsequence is empty and no \cd{:initial-value} is given,
then the \emph{function} is called with zero
arguments, and \cdf{reduce} returns whatever the function does.  (This is
the only case where the \emph{function} is called with other than two
arguments.)

\begin{lisp}
(reduce \#'+ '(1 2 3 4)) \EV\ 10 \\
(reduce \#'- '(1 2 3 4)) \EQ\ (- (- (- 1 2) 3) 4) \EV\ -8 \\
(reduce \#'- '(1 2 3 4) :from-end t)~~~~~;\textrm{Alternating sum} \\
~~~\EQ\ (- 1 (- 2 (- 3 4))) \EV\ -2 \\
(reduce \#'+ '()) \EV\ 0 \\
(reduce \#'+ '(3)) \EV\ 3 \\
(reduce \#'+ '(foo)) \EV\ foo \\
(reduce \#'list '(1 2 3 4)) \EV\ (((1 2) 3) 4) \\
(reduce \#'list '(1 2 3 4) :from-end t) \EV\ (1 (2 (3 4))) \\
(reduce \#'list '(1 2 3 4) :initial-value 'foo) \\
~~~\EV\ ((((foo 1) 2) 3) 4) \\
(reduce \#'list '(1 2 3 4) \\
~~~~~~~~:from-end t :initial-value 'foo) \\
~~~\EV\ (1 (2 (3 (4 foo))))
\end{lisp}
If the \emph{function} produces side effects, the order of the calls
to the \emph{function} can be correctly predicted from the reduction ordering
demonstrated above.

The name ``reduce'' for this function is borrowed from {APL}.

\begin{new}
X3J13 voted in March 1988 \issue{REDUCE-ARGUMENT-EXTRACTION}
to extend the \cdf{reduce} function to take
an additional keyword argument named \cd{:key}.  As usual, this argument
defaults to the identity function.  The value of this argument must be
a function that accepts at least one argument.  This function is applied once
to each element of the
sequence that is to participate in the reduction operation, in the order
implied by the \cd{:from-end} argument; the values returned by this
function are combined by the reduction \emph{function}.
However, the \cd{:key} function is \emph{not} applied
to the \cd{:initial-value} argument (if any).
\end{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}
\end{defun}

\section{Modifying Sequences}

Each of these functions alters the contents of a sequence or produces
an altered copy of a given sequence.

\begin{defun}[Function]
fill sequence item &key :start :end

The \emph{sequence} is destructively modified by replacing each element of
the subsequence specified by the \cd{:start} and \cd{:end} parameters
with the \emph{item}.  The \emph{item} may be any Lisp object but must be a
suitable element for the \emph{sequence}.  The \emph{item} is stored into all
specified components of the \emph{sequence}, beginning at the one specified
by the \cd{:start} index (which defaults to zero), up to but not
including the one specified by the \cd{:end} index (which defaults to the
length of the sequence).  \cdf{fill} returns the modified \emph{sequence}.
For example:
\begin{lisp}
(setq x (vector 'a 'b 'c 'd 'e)) \EV\ \#(a b c d e) \\
(fill x 'z \cd{:start} 1 \cd{:end} 3) \EV\ \#(a z z d e) \\
~~\textrm{and now} x \EV\ \#(a z z d e) \\
(fill x 'p) \EV\ \#(p p p p p) \\
~~\textrm{and now} x \EV\ \#(p p p p p)
\end{lisp}
\end{defun}

\begin{defun}[Function]
replace sequence1 sequence2 &key :start1 :end1 :start2~:end2

The sequence \emph{sequence1} is destructively modified by copying successive
elements into it from \emph{sequence2}.  The elements of
\emph{sequence2} must be of a type that may be stored into
\emph{sequence1}.  The subsequence of \emph{sequence2}
specified by \cd{:start2} and \cd{:end2} is copied into the
subsequence of \emph{sequence1} specified by \cd{:start1} and \cd{:end1}.
(The arguments \cd{:start1} and \cd{:start2} default to zero.
The arguments \cd{:end1} and \cd{:end2} default
to {\false}, meaning the end of the appropriate sequence.)
If these subsequences are not of the same length, then
the shorter length determines how many elements are copied; the extra
elements near the end of the longer subsequence are not involved in the
operation.
The number of elements copied may be expressed as:
\begin{lisp}
(min (- \emph{end1} \emph{start1}) (- \emph{end2} \emph{start2}))
\end{lisp}
The value returned by \cdf{replace} is the modified \emph{sequence1}.

If \emph{sequence1} and \emph{sequence2} are the same (\cdf{eq}) object
and the region being modified overlaps the region being copied
from, then it is as if the entire source region were copied to another
place and only then copied back into the target region.
However, if \emph{sequence1} and \emph{sequence2} are \emph{not} the same,
but the region being modified overlaps the region being copied from
(perhaps because of shared list structure or displaced arrays),
then after the \cdf{replace} operation
the subsequence of \emph{sequence1} being modified will have
unpredictable contents.
\end{defun}

\begin{defun}[Function]
remove item sequence &key :from-end :test :test-not :start :end :count :key \\
remove-if predicate sequence &key :from-end :start :end :count :key \\
remove-if-not predicate sequence &key :from-end :start :end :count :key

The result is a sequence of the same kind as the argument \emph{sequence}
that has the same elements except that those in the subsequence
delimited by \cd{:start} and \cd{:end} and satisfying the test (see
above) have been removed.  This is a non-destructive operation; the result
is a copy of the input \emph{sequence}, save that some elements are not
copied.  Elements not removed occur in the same order in the result
as they did in the argument.

The \cd{:count} argument, if supplied, limits the number of elements
removed; if more than \cd{:count} elements satisfy the test,
then of these elements only the leftmost are removed,
as many as specified by \cd{:count}.

\begin{new}
X3J13 voted in January 1989
\issue{RANGE-OF-COUNT-KEYWORD}
to clarify that the \cd{:count} argument must be either \cdf{nil}
or an integer, and that supplying a negative integer produces the
same behavior as supplying zero.
\end{new}

A non-{\false} \cd{:from-end} specification
matters only when the \cd{:count} argument
is provided; in that case only the rightmost \cd{:count} elements satisfying
the test are removed.
For example:
\begin{lisp}
(remove 4 '(1 2 4 1 3 4 5)) \EV\ (1 2 1 3 5) \\
(remove 4 '(1 2 4 1 3 4 5) \cd{:count} 1) \EV\ (1 2 1 3 4 5) \\
(remove 4 '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 5) \\
(remove 3 '(1 2 4 1 3 4 5) \cd{:test} \#'>) \EV\ (4 3 4 5) \\
(remove-if \#'oddp '(1 2 4 1 3 4 5)) \EV\ (2 4 4) \\
(remove-if \#'evenp '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 5)
\end{lisp}
The result of \cdf{remove} may share
with the argument \emph{sequence}; a list result may share a tail
with an input list, and the result may be \cdf{eq} to the input \emph{sequence}
if no elements need to be removed.

\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]
delete item sequence &key :from-end :test :test-not :start~:end~:count~:key \\
delete-if predicate sequence &key :from-end :start~:end~:count~:key \\
delete-if-not predicate sequence &key :from-end :start~:end~:count~:key

This is the destructive counterpart to \cdf{remove}.
The result is a sequence of the same kind as the argument \emph{sequence}
that has the same elements except that those in the subsequence
delimited by \cd{:start} and \cd{:end} and satisfying the test (see
above) have been deleted.  This is a destructive operation.
The argument \emph{sequence} may be destroyed and used to construct
the result; however, the result may or may not be \cdf{eq} to \emph{sequence}.
Elements not deleted occur in the same order in the result
as they did in the argument.

The \cd{:count} argument, if supplied, limits the number of elements
deleted; if more than \cd{:count} elements satisfy the test,
then of these elements only the leftmost are deleted,
as many as specified by \cd{:count}.

\begin{new}
X3J13 voted in January 1989
\issue{RANGE-OF-COUNT-KEYWORD}
to clarify that the \cd{:count} argument must be either \cdf{nil}
or an integer, and that supplying a negative integer produces the
same behavior as supplying zero.
\end{new}

A non-{\false} \cd{:from-end} specification
matters only when the \cd{:count} argument
is provided; in that case only the rightmost \cd{:count} elements satisfying
the test are deleted.
For example:
\begin{lisp}
(delete 4 '(1 2 4 1 3 4 5)) \EV\ (1 2 1 3 5) \\
(delete 4 '(1 2 4 1 3 4 5) \cd{:count} 1) \EV\ (1 2 1 3 4 5) \\
(delete 4 '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 5) \\
(delete 3 '(1 2 4 1 3 4 5) \cd{:test} \#'>) \EV\ (4 3 4 5) \\
(delete-if \#'oddp '(1 2 4 1 3 4 5)) \EV\ (2 4 4) \\
(delete-if \#'evenp '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 5)
\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}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations.
When the \emph{sequence} is a list,
\cdf{delete} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of that list.
When the \emph{sequence} is an array,
\cdf{delete} is permitted to alter the dimensions of the given array
and to slide some of its elements into new positions without permuting them
in order to produce the resulting array.

Furthermore, \cd{(delete-if \emph{predicate} \emph{sequence}~...)}
is required to behave exactly like
\begin{lisp}
(delete nil \emph{sequence} \\*
~~~~~~~~:test \#'(lambda (unused item) \\*
~~~~~~~~~~~~~~~~~~~(declare (ignore unused)) \\*
~~~~~~~~~~~~~~~~~~~(funcall \emph{predicate} item)) \\*
~~~~~~~~...)
\end{lisp}
\end{newer}
\end{defun}

\begin{defun}[Function]
remove-duplicates sequence &key :from-end :test :test-not :start :end :key \\
delete-duplicates sequence &key :from-end :test :test-not :start :end :key

The elements of \emph{sequence} are compared pairwise, and if any two match,
then the one occurring earlier in the sequence
is discarded (but if the \cd{:from-end} argument is true, then the one
later in the sequence is discarded).
The result is a sequence of the same kind as the
argument sequence with enough elements removed so that no two of the remaining
elements match.  The order of the elements remaining in the result
is the same as the order in which they appear in \emph{sequence}.

\cdf{remove-duplicates} is the non-destructive version
of this operation.
The result of \cdf{remove-duplicates} may share
with the argument \emph{sequence}; a list result may share a tail
with an input list, and the result may be \cdf{eq} to the input \emph{sequence}
if no elements need to be removed.

\cdf{delete-duplicates} may destroy the argument \emph{sequence}.

Some examples:
\begin{lisp}
(remove-duplicates '(a b c b d d e)) \EV\ (a c b d e) \\
(remove-duplicates '(a b c b d d e) \cd{:from-end} t) \EV\ (a b c d e) \\
(remove-duplicates '((foo \#{\Xbackslash}a) (bar \#{\Xbackslash}\%) (baz \#{\Xbackslash}A)) \\
~~~~~~~~~~~~~~~~~~~\cd{:test} \#'char-equal \cd{:key} \#'cadr) \\
~~~\EV\ ((bar \#{\Xbackslash}\%) (baz \#{\Xbackslash}A)) \\
(remove-duplicates '((foo \#{\Xbackslash}a) (bar \#{\Xbackslash}\%) (baz \#{\Xbackslash}A)) \\
~~~~~~~~~~~~~~~~~~~\cd{:test} \#'char-equal \cd{:key} \#'cadr \cd{:from-end} t) \\
~~~\EV\ ((foo \#{\Xbackslash}a) (bar \#{\Xbackslash}\%))
\end{lisp}

These functions are useful for converting a sequence into a canonical
form suitable for representing a set.

\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.
When the \emph{sequence} is a list,
\cdf{delete-duplicates} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of that list.
When the \emph{sequence} is an array,
\cdf{delete-duplicates} is permitted to alter the dimensions of the given array
and to slide some of its elements into new positions without permuting them
in order to produce the resulting array.
\end{newer}
\end{defun}

\begin{defun}[Function]
substitute newitem olditem sequence &key :from-end :test :test-not :start :end :count :key \\
substitute-if newitem test sequence &key :from-end :start~:end :count :key \\
substitute-if-not newitem test sequence &key :from-end :start :end :count :key

The result is a sequence of the same kind as the argument \emph{sequence}
that has the same elements except that those in the subsequence
delimited by \cd{:start} and \cd{:end} and satisfying the test (see
above) have been replaced by \emph{newitem}.  This is a non-destructive
operation; the result is a copy of the input \emph{sequence}, save that some
elements are changed.

The \cd{:count} argument, if supplied, limits the number of elements
altered; if more than \cd{:count} elements satisfy the test,
then of these elements only the leftmost are replaced,
as many as specified by \cd{:count}.

\begin{new}
X3J13 voted in January 1989
\issue{RANGE-OF-COUNT-KEYWORD}
to clarify that the \cd{:count} argument must be either \cdf{nil}
or an integer, and that supplying a negative integer produces the
same behavior as supplying zero.
\end{new}

A non-{\false} \cd{:from-end} specification
matters only when the \cd{:count} argument
is provided; in that case only the rightmost \cd{:count} elements satisfying
the test are replaced.
For example:
\begin{lisp}
(substitute 9 4 '(1 2 4 1 3 4 5)) \EV\ (1 2 9 1 3 9 5) \\
(substitute 9 4 '(1 2 4 1 3 4 5) \cd{:count} 1) \EV\ (1 2 9 1 3 4 5) \\
(substitute 9 4 '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 9 5) \\
(substitute 9 3 '(1 2 4 1 3 4 5) \cd{:test} \#'>) \EV\ (9 9 4 9 3 4 5) \\
(substitute-if 9 \#'oddp '(1 2 4 1 3 4 5)) \EV\ (9 2 4 9 9 4 9) \\
(substitute-if 9 \#'evenp '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 9 5)
\end{lisp}
The result of \cdf{substitute} may share
with the argument \emph{sequence}; a list result may share a tail
with an input list, and the result may be \cdf{eq} to the input \emph{sequence}
if no elements need to be changed.

See also \cdf{subst}, which performs substitutions throughout a 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}

\begin{defun}[Function]
nsubstitute newitem olditem sequence &key :from-end :test :test-not :start :end :count :key \\
nsubstitute-if newitem test sequence &key :from-end :start~:end :count :key \\
nsubstitute-if-not newitem test sequence &key :from-end :start :end :count :key

This is the destructive counterpart to \cdf{substitute}.
The result is a sequence of the same kind as the argument \emph{sequence}
that has the same elements except that those in the subsequence
delimited by \cd{:start} and \cd{:end} and satisfying the test (see
above) have been replaced by \emph{newitem}.  This is a destructive operation.
The argument \emph{sequence} may be destroyed and used to construct
the result; however, the result may or may not be \cdf{eq} to \emph{sequence}.

See also \cdf{nsubst}, which performs destructive
substitutions throughout a 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}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations.
When the \emph{sequence} is a list,
\cdf{nsubstitute} or \cdf{nsubstitute-if}
is required to perform a \cdf{setf} on any
\emph{car} of the top-level list structure of that list
whose old contents must be replaced with \emph{newitem}
but is forbidden to perform a \cdf{setf} on any \cdf{cdr} of the list.
When the \emph{sequence} is an array,
\cdf{nsubstitute} or \cdf{nsubstitute-if}
is required to perform a \cdf{setf} on any element of the array
whose old contents must be replaced with \emph{newitem}.
These functions, therefore, may successfully be
used solely for effect, the caller discarding the returned value
(though some programmers find this stylistically distasteful).
\end{newer}
\end{defun}

\section{Searching Sequences for Items}

Each of these functions searches a sequence to locate one or more
elements satisfying some test.

\begin{defun}[Function]
find item sequence &key :from-end :test :test-not :start~:end :key \\
find-if predicate sequence &key :from-end :start :end :key \\
find-if-not predicate sequence &key :from-end :start~:end~:key

If the \emph{sequence} contains an element satisfying the test,
then the leftmost such element
is returned; otherwise {\false} is returned.

If \cd{:start} and \cd{:end} keyword arguments are given,
only the specified subsequence of \emph{sequence} is searched.

If a non-{\false} \cd{:from-end} keyword argument is specified, then the result is
the \emph{rightmost} element satisfying 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]
position item sequence &key :from-end :test :test-not :start~:end~:key \\
position-if predicate sequence &key :from-end :start~:end~:key \\
position-if-not predicate sequence &key :from-end :start~:end~:key

If the \emph{sequence} contains an element satisfying the test,
then the index within the sequence of the leftmost such element
is returned as a non-negative integer; otherwise {\false} is returned.

If \cd{:start} and \cd{:end} keyword arguments are given,
only the specified subsequence of \emph{sequence} is searched.
However, the index returned is relative to the entire sequence,
not to the subsequence.

If a non-{\false} \cd{:from-end} keyword argument is specified, then the result is
the index of the \emph{rightmost} element satisfying the test.  (The index
returned, however, is an index from the left-hand end, as usual.)

\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}

Here is a simple piece of code that uses several of the sequence
functions, notably \cdf{position-if} and \cdf{find-if},
to process strings.  Note one use of \cdf{loop} as well.
\begin{lisp}
(defun debug-palindrome (s) \\*
~~(flet ((match (x) (char-equal (first x) (third x)))) \\*
~~~~(let* ((pairs (loop for c across s \\*
~~~~~~~~~~~~~~~~~~~~~~~~for j from 0 \\*
~~~~~~~~~~~~~~~~~~~~~~~~when (alpha-char-p c) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~collect (list c j))) \\*
~~~~~~~~~~~(quads (mapcar \#'append pairs (reverse pairs))) \\*
~~~~~~~~~~~(diffpos (position-if (complement \#'match) quads))) \\
~~~~~~(when diffpos \\*
~~~~~~~~(let* ((diff (elt quads diffpos)) \\*
~~~~~~~~~~~~~~~(same (find-if \#'match quads \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~:start (+ diffpos 1)))) \\
~~~~~~~~~~(if same \\*
~~~~~~~~~~~~~~(format nil \\*
~~~~~~~~~~~~~~~~~~~~~~"/{\Xtilde}A/ (at {\Xtilde}D) is not the reverse of /{\Xtilde}A/" \\*
~~~~~~~~~~~~~~~~~~~~~~(subseq s (second diff) (second same)) \\*
~~~~~~~~~~~~~~~~~~~~~~(second diff) \\*
~~~~~~~~~~~~~~~~~~~~~~(subseq s (+ (fourth same) 1) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(+ (fourth diff) 1))) \\*
~~~~~~~~~~~~~~"This palindrome is completely messed up!"))))))
\end{lisp}
Here is an example of its behavior.
\begin{lisp}
(setq panama~~~~~;\textrm{A putative palindrome?} \\*
~~~~~~"A man, a plan, a canoe, pasta, heros, rajahs, \\*
~~~~~~~a coloratura, maps, waste, percale, macaroni, a gag, \\*
~~~~~~~a banana bag, a tan, a tag, a banana bag again \\*
~~~~~~~(or a camel), a crepe, pins, Spam, a rut, a Rolo, \\*
~~~~~~~cash, a jar, sore hats, a peon, a canal--Panama!")
\end{lisp}
\begin{lisp}
(debug-palindrome panama) \\*
~~\EV\ "/wast/ (at 73) is not the reverse of /, pins/" \\
\\
(replace panama "snipe" :start1 73)~~~~~;\textrm{Repair it} \\*
~~\EV\ "A man, a plan, a canoe, pasta, heros, rajahs, \\*
~~~~~~~a coloratura, maps, snipe, percale, macaroni, a gag, \\*
~~~~~~~a banana bag, a tan, a tag, a banana bag again \\*
~~~~~~~(or a camel), a crepe, pins, Spam, a rut, a Rolo, \\*
~~~~~~~cash, a jar, sore hats, a peon, a canal--Panama!" \\
\\
(debug-palindrome panama) \EV\ nil~~~~~;\textrm{Copacetic---a true palindrome} \\
\\
(debug-palindrome "Rubber baby buggy bumpers") \\*
~~\EV\ "/Rubber / (at 0) is not the reverse of /umpers/" \\
\\
(debug-palindrome "Common Lisp: The Language") \\*
~~\EV\ "/Commo/ (at 0) is not the reverse of /guage/" \\
\\
(debug-palindrome "Complete mismatches are hard to find") \\*
~~\EV\ \\
~~"/Complete mism/ (at 0) is not the reverse of /re hard to find/" \\
\\
(debug-palindrome "Waltz, nymph, for quick jigs vex Bud") \\*
~~\EV\ "This palindrome is completely messed up!" \\
\\
(debug-palindrome "Doc, note: I dissent.~~A fast never \\*
~~~~~~~~~~~~~~~~~~~prevents a fatness.~~I diet on cod.") \\*
~~\EV\nil~~~~~;\textrm{Another winner} \\
\\
(debug-palindrome "Top step's pup's pet spot") \EV\ nil
\end{lisp}

\begin{defun}[Function]
count item sequence &key :from-end :test :test-not :start~:end~:key \\
count-if predicate sequence &key :from-end :start~:end~:key \\
count-if-not predicate sequence &key :from-end :start~:end~:key

The result is always a non-negative integer, the number of
elements in the specified subsequence of \emph{sequence} satisfying
the test.

The \cd{:from-end} argument does not affect the result returned;
it is accepted purely for compatibility with other sequence functions.

\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]
mismatch sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2

The specified subsequences of
\emph{sequence1} and \emph{sequence2} are compared element-wise.
If they are of equal length and match in every element, the result is
{\false}.  Otherwise, the result is a non-negative integer.
This result is the index within
\emph{sequence1} of the leftmost position at which the two
subsequences fail to match; or,
if one subsequence is shorter than and a matching prefix of the other,
the result is the index
relative to \emph{sequence1} beyond the last position tested.

If a non-{\false} \cd{:from-end} keyword argument is given, then
\emph{one plus} the index of the \emph{rightmost}
position in which the sequences differ is returned.  In effect, the (sub)sequences
are aligned at their right-hand ends; then, the last elements are compared,
the penultimate elements, and so on.  The index returned is again
an index relative to \emph{sequence1}.

\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]
search sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2

A search is conducted for a subsequence of \emph{sequence2} that
element-wise matches \emph{sequence1}.
If there is no such subsequence, the result is {\false}; if there is,
the result is the index into \emph{sequence2} of the leftmost element
of the leftmost such matching subsequence.

If a non-{\false} \cd{:from-end} keyword argument is given,
the index of the leftmost
element of the \emph{rightmost} matching subsequence is returned.

The implementation may choose to search the sequence in any order;
there is no guarantee on the number of times the test is made.
For example, \cdf{search} with a non-{\nil} \cd{:from-end}
argument might actually search a list from left to right
instead of from right to left (but in either case would return
the rightmost matching subsequence, of course).  Therefore it is a good
idea for a user-supplied predicate to be free of side effects.

\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{Sorting and Merging}

These functions may destructively modify argument sequences
in order to put a sequence into sorted order or to merge two
already sorted sequences.

\begin{defun}[Function]
sort sequence predicate &key :key \\
stable-sort sequence predicate &key :key

\indexterm{sorting}
The \emph{sequence} is destructively sorted according to an order determined by
the \emph{predicate}.  The \emph{predicate} should take two
arguments, and return non-{\false} if and only if the first argument is
strictly less than the second (in some appropriate sense). 
If the first argument is greater than or equal to the second
(in the appropriate sense), then the \emph{predicate} should return {\false}.

The \cdf{sort} function determines the relationship between two elements
by giving keys extracted from the elements to the \emph{predicate}.
The \cd{:key} argument, when applied to an element, should return
the key for that element.  The \cd{:key} argument defaults to the identity
function, thereby making the element itself be the key.

The \cd{:key} function should not have any side effects.
A useful example of a \cd{:key} function would be a component
selector function for a \cdf{defstruct} structure, used in sorting
a sequence of structures.
\begin{lisp}
(sort \emph{a} \emph{p} \cd{:key} \emph{s})
   \EQ\ (sort \emph{a} \#'(lambda (x y) (\emph{p} (\emph{s} x) (\emph{s} y))))
\end{lisp}
While the above two expressions are equivalent, the first may be more
efficient in some implementations for certain types of arguments.  For
example, an implementation may choose to apply \emph{s} to each
item just once, putting the resulting keys into a separate table, and
then sort the parallel tables, as opposed to applying
\emph{s} to an item every time just before applying the \emph{predicate}.

If the \cd{:key} and \emph{predicate} functions always return, then the
sorting operation will always terminate, producing a sequence containing
the same elements as the original sequence (that is, the result is a
permutation of \emph{sequence}).  This is guaranteed even if the
\emph{predicate} does not really consistently represent a total order
(in which case the elements will be scrambled in some unpredictable
way, but no element will be lost).  If
the \cd{:key} function consistently returns meaningful keys,
and the \emph{predicate}
does reflect some total ordering criterion on those keys, then the
elements of the result sequence will be properly sorted according
to that ordering.

The sorting operation performed by \cdf{sort} is not guaranteed \emph{stable}.
Elements considered equal by the \emph{predicate} may or may not
stay in their original order.  (The \emph{predicate} is assumed to
consider two elements \emph{x} and \emph{y} to be equal if
\cd{(funcall \emph{predicate} \emph{x} \emph{y})} and
\cd{(funcall \emph{predicate} \emph{y} \emph{x})} are both false.)
The function \cdf{stable-sort} guarantees
stability but may be slower than \cdf{sort} in some situations.

The sorting operation may be destructive in all cases.  In the case of an
array argument, this is accomplished by permuting the elements in place.
In the case of a list, the list is
destructively reordered in the same manner as for
\cdf{nreverse}.  Thus if the argument should not be destroyed, the
user must sort a copy of the argument.

Should execution of the \cd{:key} function or the \emph{predicate} cause an error,
the state of the list or array being sorted is
undefined.  However, if the error is corrected, the sort will, of
course, proceed correctly. 

Note that since sorting requires many comparisons, and thus
many calls to the \emph{predicate}, sorting will be much faster if the
\emph{predicate} is a compiled function rather than interpreted. 

An example:
\begin{lisp}
(setq foovector (sort foovector \#'string-lessp \cd{:key} \#'car))
\end{lisp}
If \cdf{foovector} contained these items before the sort
\begin{lisp}
("Tokens" "The Lion Sleeps Tonight") \\
("Carpenters" "Close to You") \\
("Rolling Stones" "Brown Sugar") \\
("Beach Boys" "I Get Around") \\
("Mozart" "Eine Kleine Nachtmusik" (K 525)) \\
("Beatles" "I Want to Hold Your Hand")
\end{lisp}
then after the sort \cdf{foovector} would contain
\begin{lisp}
("Beach Boys" "I Get Around") \\
("Beatles" "I Want to Hold Your Hand") \\
("Carpenters" "Close to You") \\
("Mozart" "Eine Kleine Nachtmusik" (K 525)) \\
("Rolling Stones" "Brown Sugar") \\
("Tokens" "The Lion Sleeps Tonight")
\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]
merge result-type sequence1 sequence2 predicate &key :key

The sequences \emph{sequence1} and \emph{sequence2} are destructively
merged according to an order determined by
the \emph{predicate}.  The result is a sequence of type \emph{result-type},
which must be a subtype of \cdf{sequence}, as for the function \cdf{coerce}.
The \emph{predicate} should take two
arguments and return non-{\false} if and only if the first argument is
strictly less than the second (in some appropriate sense). 
If the first argument is greater than or equal to the second
(in the appropriate sense), then the \emph{predicate} should return {\false}.

The \cdf{merge} function determines the relationship between two elements
by giving keys extracted from the elements to the \emph{predicate}.
The \cd{:key} function, when applied to an element, should return
the key for that element; the \cd{:key} function defaults to the identity
function, thereby making the element itself be the key.

The \cd{:key} function should not have any side effects.
A useful example of a \cd{:key} function would be a component
selector function for a \cdf{defstruct} structure, used to merge
a sequence of structures.

If the \cd{:key} and \emph{predicate} functions always return, then the
merging operation will always terminate.
The result of merging two sequences \emph{x} and \emph{y} is a new sequence
\emph{z}, such that the length of \emph{z} is the sum of the lengths of \emph{x}
and \emph{y}, and \emph{z} contains all the elements of \emph{x} and \emph{y}.
If \emph{x1} and \emph{x2} are two elements of \emph{x}, and \emph{x1} precedes
\emph{x2} in \emph{x}, then \emph{x1} precedes \emph{x2} in \emph{z}, and similarly for
elements of \emph{y}.  In short, \emph{z} is an \emph{interleaving} of \emph{x}
 and \emph{y}.

Moreover, if \emph{x} and \emph{y} were correctly sorted according to the
\emph{predicate}, then \emph{z} will also be correctly sorted,
as shown in this example.
\begin{lisp}
(merge 'list '(1 3 4 6 7) '(2 5 8) \#'<) \EV\ (1 2 3 4 5 6 7 8)
\end{lisp}
If \emph{x} or \emph{y} is not so sorted then \emph{z} will not be sorted,
but will nevertheless be an interleaving of \emph{x} and \emph{y}.

The merging operation is guaranteed
\emph{stable}; if two or more elements are considered equal by the
\emph{predicate}, then the elements from \emph{sequence1} will
precede those from \emph{sequence2} in the result.
(The \emph{predicate} is assumed to
consider two elements \emph{x} and \emph{y} to be equal if
\cd{(funcall \emph{predicate} \emph{x} \emph{y})} and
\cd{(funcall \emph{predicate} \emph{y} \emph{x})} are both false.)
For example:
\begin{lisp}
(merge 'string "BOY" "nosy" \#'char-lessp) \EV\ "BnOosYy"
\end{lisp}
The result can \emph{not} be \cd{"BnoOsYy"}, \cd{"BnOosyY"}, or \cd{"BnoOsyY"}.
The function \cdf{char-lessp} ignores case, and so considers
the characters \cdf{Y} and \cdf{y} to be equal, for example;
the stability property then guarantees that the character from the
first argument (\cdf{Y}) must precede the one from the second
argument (\cdf{y}).

\begin{newer}
X3J13 voted in June 1989 \issue{SEQUENCE-TYPE-LENGTH} to specify that
\cdf{merge} should signal an error if the sequence type specifies the number of
elements and the sum of the lengths of the two sequence arguments is
different.
\end{newer}

\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{Последовательности}
\label{KSEQUE}

Тип \cdf{sequence} объединяет списки и вектора (одномерные массивы).
Хотя это две различные структуры данных с различными структурными
свойствами, приводящими к алгоритмически различному использованию, они имеют
общее свойство: каждая хранит упорядоченное множество элементов.

Некоторые операции полезны и для списков и для массивов, потому что они
взаимодействуют с упорядоченными множествами элементов. Можно запросить
количество элементов, изменить порядок элементов на противоположный, извлечь
подмножество (подпоследовательность) и так далее. Для таких целей Common Lisp
предлагает ряд общих для всех типов последовательностей функций.

\begin{flushleft}
\begin{tabular*}{\textwidth}{@{}l@{\extracolsep{\fill}}lll@{}}
\cdf{elt}&\cdf{reverse}&\cdf{map}&\cdf{remove} \\
\cdf{length}&\cdf{nreverse}&\cdf{some}&\cdf{remove-duplicates} \\
\cdf{subseq}&\cdf{concatenate}&\cdf{every}&\cdf{delete} \\
\cdf{copy-seq}&\cdf{position}&\cdf{notany}&\cdf{delete-duplicates} \\
\cdf{fill}&\cdf{find}&\cdf{notevery}&\cdf{substitute} \\
\cdf{replace}&\cdf{sort}&\cdf{reduce}&\cdf{nsubstitute} \\
\cdf{count}&\cdf{merge}&\cdf{search}&\cdf{mismatch}
\end{tabular*}
\end{flushleft}
Некоторые из этих операций имеют более одной версии.
Такие версии отличаются суффиксом (или префиксом) от имени базовой функции.
Кроме того, многие операции принимают один или более необязательных именованных
аргументов, которые могут изменить поведение операции.

Если операция требует проверки элементов последовательности на совпадение с
некоторым условием, тогда это условие может быть указано одним из двух способов.
Основная операция принимает объект и сравнивает с ним каждый элемент
последовательности на равенство \cdf{eql}.
(Операция сравнения может быть задана в именованном параметре \cd{:test} или
\cd{:test-not}. Использование обоих параметров одновременно является ошибкой.)
Другие варианты операции образуются с добавлением префиксов \cdf{-if} и
\cdf{-if-not}. Эти операции, в отличие от базовой, принимают не объект, а
предикат с одним аргументом. В этом случае проверяется истинность или ложность
предиката для каждого элемента последовательности.
В качестве примера,
\begin{lisp}
(remove \emph{item} \emph{sequence})
\end{lisp}
возвращает копию последовательности \emph{sequence}, в которой удалены все
элементы равные \cdf{eql} объекту \emph{emph}.
\begin{lisp}
(remove \emph{item} \emph{sequence} \cd{:test} \#'equal)
\end{lisp}
возвращает копию последовательности \emph{sequence}, в которой удалены все
элементы равные \cdf{equal} объекту \emph{emph}.
\begin{lisp}
(remove-if \#'numberp \emph{sequence})
\end{lisp}
возвращает копию последовательности \emph{sequence}, в которой удалены все
числа.

Если операция любым методом проверяет элементы последовательности, 
то если именованный параметр \cdf{:key} не равняется {\false}, то он должен быть
функцией одного аргумента, которая будет извлекать из элемента необходимую для
проверки часть.
Например,
\begin{lisp}
(find \emph{item} \emph{sequence} \cd{:test} \#'eq \cd{:key} \#'car)
\end{lisp}
Это выражение ищет первый элемент последовательности \emph{sequence}, \emph{car}
элемент которого равен \cdf{eq} объекту \emph{item}.

\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to allow the \cd{:key} function
to be only of type \cdf{symbol} or \cdf{function}; a lambda-expression
is no longer acceptable as a functional argument.  One must use the
\cdf{function} special operator or the abbreviation \cd{\#'} before
a lambda-expression that appears as an  explicit argument form.
\end{newer}

Для некоторых операций было бы удобно указать направление обработки
последовательности. В этом случае базовые операции обычно обрабатывают
последовательность в прямом направлении. Обратное направление обработки
указывается с помощью не-{\false} значения для именованного параметра
\cd{:from-end}. (Порядок обработки указываемый в \cd{:from-end} чисто
концептуальный. В зависимости от обрабатываемого объекта и реализации,
действительный порядок обработки может отличаться. Поэтому пользовательские
функции \emph{test} не должны иметь побочных эффектов.)

Много операций позволяют указать подпоследовательность для обработки. Такие
операции имеют именованные параметры \cd{:start} и \cd{:end}. Эти аргумент
должны быть индексами внутри последовательности, и
$\emph{start}\leq\emph{end}$. Ситуация $\emph{start}>\emph{end}$ является
ошибкой. Эти параметры указывают подпоследовательность начиная с позиции \emph{start}
включительно и заканчивая позицией \emph{end} невключительно. Таким образом
длина подпоследовательности равна $\emph{end}-\emph{start}$. Если параметр
\emph{start} опущен, используется значение по-умолчанию ноль. Если параметр
\emph{end} опущен, используется значение по-умолчанию длина последовательности.
В большинстве случаев, указание подпоследовательности допускается исключительно
ради эффективности. Вместо этого можно было бы просто вызвать
\cdf{subseq}. Однако, следует отметить, что операция, которая вычисляет индексы
для подпоследовательности, возвращает индексы исходной последовательности, а не
подпоследовательности:
\begin{lisp}
(position \#{\Xbackslash}b "foobar" \cd{:start} 2 \cd{:end} 5) \EV\ 3 \\
(position \#{\Xbackslash}b (subseq "foobar" 2 5)) \EV\ 1
\end{lisp}
Если в операции участвует две последовательности, тогда ключевые параметры
\cd{:start1}, \cd{:end1}, \cd{start2} и \cd{:end2} используются для указания
отдельных подпоследовательностей для каждой последовательности.

\begin{newer}
X3J13 voted in June 1988 \issue{SUBSEQ-OUT-OF-BOUNDS}
(and further clarification was voted in January 1989
\issue{RANGE-OF-START-AND-END-PARAMETERS})
to specify that these rules apply not
only to all built-in functions that have keyword parameters named
\cd{:start}, \cd{:start1}, \cd{:start2}, \cd{:end}, \cd{:end1},
or \cd{:end2} but also to functions such as \cdf{subseq}
that take required or optional parameters that are documented
as being named \emph{start} or \emph{end}.
\begin{itemize}
\item A ``start'' argument must always be a non-negative integer and
defaults to zero if not supplied; it is not permissible to pass \cdf{nil}
as a ``start'' argument.
\item An ``end'' argument must be either a
non-negative integer or \cdf{nil} (which indicates the end of the
sequence) and defaults to \cdf{nil}
if not supplied; therefore supplying \cdf{nil} is equivalent to
not supplying such an argument.
\item If the ``end'' argument is an integer, it must be no greater than the
active length of the corresponding sequence
(as returned by the function \cdf{length}).
\item The default value for the ``end'' argument is the active length
of the corresponding sequence.
\item The ``start'' value (after defaulting, if necessary) must not be greater than the
corresponding ``end'' value (after defaulting, if necessary).
\end{itemize}
This may be summarized as follows.
Let \emph{x} be the sequence within which indices are to be considered.  Let \emph{s} be
the ``start'' argument for that sequence of any standard function,
whether explicitly specified or defaulted, through omission, to
zero.  Let \emph{e} be the ``end'' argument for that sequence
of any standard function, whether explicitly specified or defaulted, through
omission or an explicitly passed \cdf{nil} value, to the active length of \emph{x}, as
returned by \cdf{length}.  Then it is an error if the test
\cd{(<=~0~\emph{s}~\emph{e}~(length \emph{x}))}
is not true.
\end{newer}

Для некоторых функций, в частности \cdf{remove} и \cdf{delete}, ключевой
параметр \cd{:count} используется для указания, как много подходящих элементов
должны обрабатываться. Если он равен {\false} или не указан, обрабатываются все
подходящие элементы.

В следующих описаниях функций, элемент \emph{x} последовательности
<<удовлетворяет условию>>, если любое из следующих выражений верно:
\begin{itemize}
\item
Была вызвана базовая функция, 
функция \emph{testfn} заданная в параметре \cd{:test}, и 
выражение \cd{(funcall \emph{testfn} \emph{item} (\emph{keyfn} \emph{x}))}
истинно.

\item
Была вызвана базовая функция, 
функция \emph{testfn}  заданная в параметре \cd{:test-not}, и
выражение \cd{(funcall \emph{testfn} \emph{item} (\emph{keyfn} \emph{x}))}
ложно.

\item
Была вызвана функция \cdf{-if}, и выражение
\cd{(funcall \emph{predicate} (\emph{keyfn} \emph{x}))} истинно.

\item
Была вызвана функция \cdf{-if-not}, и выражение
\cd{(funcall \emph{predicate} (\emph{keyfn} \emph{x}))} ложно
\end{itemize}
В каждом случае, функция \emph{keyfn} является значением параметра \cd{:key}
(по-умолчанию функцией эквивалентности). Для примера, смотрите \cdf{remove}.

В следующих описаниях функций
два элемента \emph{x} и \emph{y}, взятых из последовательности,
<<эквивалентны>>, если одно из следующих выражений верно:
\begin{itemize}
\item
Функция \emph{testfn} указана в параметре \cd{:test}, и 
выражение
\cd{(funcall \emph{testfn} (\emph{keyfn} \emph{x}) (\emph{keyfn}  \emph{y}))}
истинно.

\item
Функция \emph{testfn} указана в параметре \cd{:test-not}, и 
выражение
\cd{(funcall \emph{testfn} (\emph{keyfn} \emph{x}) (\emph{keyfn} \emph{y}))}
ложно.
\end{itemize}
Для примера, смотрите \cdf{search}.

\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to allow the \emph{testfn}
or \cdf{predicate}
to be only of type \cdf{symbol} or \cdf{function}; a lambda-expression
is no longer acceptable as a functional argument.  One must use the
\cdf{function} special operator or the abbreviation \cd{\#'} before
a lambda-expression that appears as an  explicit argument form.
\end{newer}

Вы можете рассчитывать на порядок передачи аргументов в функцию \emph{testfn}.
Это позволяет использовать некоммутативную функцию проверки в стиле предиката.
Порядок аргументов в функцию \emph{testfn} соответствует порядку, в котором эти
аргументы (или последовательности их содержащие) были переданы в рассматриваемую
функцию.
Если рассматриваемая функция передаёт два элемента из одной последовательности в
функцию \emph{testfn}, то аргументы передаются в том же порядке, в котором были
в последовательности.

Если функция должна создать и вернуть новый вектор, то она всегда возвращает
\emph{простой} вектор (смотрите раздел~\ref{ARRAY-TYPE-SECTION}).
Таким же образом, любые создаваемые строки будут простыми строками.

\begin{defun}[Function]
complement fn

Returns a function whose value is the same as that of \cdf{not}
applied to the result of applying the function \emph{fn} to the same
arguments.  One could define \cdf{complement} as follows:

Данная функция возвращает другую функцию, значение которой является
\emph{отрицанием} функции \emph{fn}. Функцию \cdf{complement} можно было
определить так:
\begin{lisp}
(defun complement (fn) \\*
~~\#'(lambda (\&rest arguments) \\*
~~~~~~(not (apply fn arguments))))
\end{lisp}

One intended use of \cdf{complement} is to supplant the use of
\cd{:test-not} arguments and \cdf{-if-not} functions.

Можно использовать функцию \cdf{complement} для эмуляции \cd{-if-not} функций
или аргумента \cd{:test-not}.
\begin{lisp}
(remove-if-not \#'virtuous senators) {\EQ} \\*
~~~(remove-if (complement \#'virtuous) senators) \\
\\
(remove-duplicates telephone-book \\*
~~~~~~~~~~~~~~~~~~~:test-not \#'mismatch) {\EQ} \\*
~~~(remove-duplicates telephone-book \\*
~~~~~~~~~~~~~~~~~~~~~~:test (complement \#'mismatch))
\end{lisp}
\end{defun}

\section{Простые функции для последовательностей}

Большинство следующих функций выполняют простые операции над одиночными
последовательностями. \cdf{make-sequence} создаёт новую последовательность.

\begin{defun}[Функция]
elt sequence index

Функция возвращает элемент последовательности \emph{sequence}, указанный
индексом \emph{index}. Индекс должен быть неотрицательным целым числом меньшим
чем длина последовательности \emph{sequence}. Длина последовательности, в свою
очередь, вычисляется функцией \cdf{length}.
Первый элемент последовательности имеет индекс \cd{0}.

(Следует отметить, что \cdf{elt} учитывает указатель заполнения для векторов,
его имеющих. Для доступа ко всем элементам таких векторов используется функция
для массивов \cdf{aref}.)

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

\begin{defun}[Функция]
subseq sequence start &optional end

Данная функция возвращает подпоследовательность последовательности
\emph{sequence} начиная с позиции \emph{start} и заканчивая позицией
\emph{end}. 
\cdf{subseq} \emph{всегда} создаёт новую последовательность для
результата. Возвращённая подпоследовательность всегда имеет тот же тип, что и
исходная последовательность.

Для изменения подпоследовательности элементов можно использовать \cdf{setf} в
связке с \cdf{subseq}. Смотрите также \cdf{replace}.
\end{defun}

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

Функция создаёт копию аргумента \emph{sequence}. Результат равен \cdf{equalp}
аргументу. Однако, результат не не равен \cdf{eq} аргументу.
\begin{lisp}
(copy-seq \emph{x}) \EQ\ (subseq \emph{x} 0)
\end{lisp}
но имя \cdf{copy-seq} лучше передаёт смысл операции.
\end{defun}

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

Функция возвращает количество элементов последовательности
\emph{sequence}. Результат является неотрицательным целым числом.
Если последовательность является вектором с указателем заполнения, возвращается
<<активная длина>>, то есть длина заданная указателем заполнения (смотрите
раздел~\ref{FILL-POINTER}).
\end{defun}

\begin{defun}[Функция]
reverse sequence

Результатом является новая последовательность такого же типа, что и
последовательность \emph{sequence}. Элементы итоговой последовательности
размещаются в обратном порядке.
Аргумент при этом не модифицируется.
\end{defun}

\begin{defun}[Функция]
nreverse sequence

Результатом является последовательность, содержащая те же элементы, что и
последовательность \emph{sequence}, но в обратном порядке. Аргумент может быть
уничтожен и использован для возврата результата. Результат может быть или не
быть равен \cdf{eq} аргументу. Поэтому обычно используют явное присваивание
\cd{(setq x (nreverse x))}, так как просто \cd{(nreverse x)} не гарантирует
возврат преобразованной последовательности в \cdf{x}.

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations.
When the \emph{sequence} is a list,
\cdf{nreverse} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of that list.
When the \emph{sequence} is an array,
\cdf{nreverse} is permitted to re-order the elements of the given array
in order to produce the resulting array.
\end{newer}
\end{defun}

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

Данная функция возвращает последовательность типа \emph{type} и длинной
\emph{size}, каждый из элементов которой содержит значение аргумента
\cd{:initial-element}.
Если указан аргумент \cd{:initial-element}, он должен принадлежать типу элемента
последовательности \emph{type}.
Например:
\begin{lisp}
(make-sequence '(vector double-float) \\*
~~~~~~~~~~~~~~~100 \\*
~~~~~~~~~~~~~~~:initial-element 1d0)
\end{lisp}
Если аргумент \cd{:initial-element} не указан, тогда последовательность
инициализируется алгоритмом реализации.

\begin{new}
X3J13 voted in January 1989
\issue{ARGUMENTS-UNDERSPECIFIED}
to clarify that the \emph{type} argument
must be a type specifier, and the \emph{size} argument
must be a non-negative integer less than the value of
\cdf{array-dimension-limit}.
\end{new}

\begin{newer}
X3J13 voted in June 1989 \issue{SEQUENCE-TYPE-LENGTH} to specify that
\cdf{make-sequence} should signal an error if the sequence \emph{type} specifies the
number of elements and the \emph{size} argument is different.
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{CHARACTER-PROPOSAL}
to specify that if \emph{type} is \cdf{string}, the result is the same
as if \cdf{make-string} had been called with the same \emph{size}
and \cd{:initial-element} arguments.
\end{newer}
\end{defun}

\section{Объединение, отображение и приведение последовательностей}

Функции в этом разделе могут обрабатывать произвольное количество
последовательностей за исключением функции \cdf{reduce}, которая была включена
сюда из-за концептуальной связи с функциями отображения.

\begin{defun}[Функция]
concatenate result-type &rest sequences

Результатом является новая последовательность, которая содержит по порядку все
элементы указанных последовательностей. Результат не содержит связей с
аргументами (в этом \cdf{concatenate} отличается от \cdf{append}). Тип
результата указывается в аргументе \emph{result-type}, который должен быть
подтипом \cdf{sequence}, как для функции \cdf{coerce}.
Необходимо, чтобы элементы исходных последовательностей принадлежали указанному
типу \emph{result-type}.

Если указана только одна последовательность, и она имеет тот же тип, что
указан в \emph{result-type}, \cdf{concatenate} всё равно копирует аргумент и
возвращает новую последовательность. Если вам не требуется копия, а просто
необходимо преобразовать тип последовательности, лучше использовать
\cdf{coerce}.

\begin{newer}
X3J13 voted in June 1989 \issue{SEQUENCE-TYPE-LENGTH} to specify that
\cdf{concatenate} should signal an error if the sequence type specifies the
number of elements and the sum of the argument lengths is different.
\end{newer}
\end{defun}

\begin{defun}[Функция]
map result-type function sequence &rest more-sequences

Функция \emph{function} должна принимать только аргументов, сколько
последовательностей было передано в \cdf{map}. 
Результат функции \cdf{map} --- последовательность, элементы которой являются
результатами применения функции \emph{function} к соответствующим элементам
исходных последовательностей. Длина итоговой последовательности равна длине
самой короткой исходной.

Если функция \emph{function} имеет побочные эффекты, она может рассчитывать на
то, что сначала будет вызвана со всеми элементами в \cd{0}-ой позиции, затем со
всеми в \cd{1}-ой и так далее.

Тип итоговой последовательности указывается в аргументе \emph{result-type} (и
должен быть подтипом \cdf{sequence}).
Кроме того, для типа можно указать {\nil}, и это означает, что результата быть
не должно. В таком случае функция \emph{function} вызывается только для побочных
эффектов, и \cdf{map} возвращает {\nil}. В этом случае \cdf{map} похожа на
\cdf{mapc}.

\begin{newer}
X3J13 voted in June 1989 \issue{SEQUENCE-TYPE-LENGTH} to specify that
\cdf{map} should signal an error if the sequence type specifies the number of
elements and the minimum of the argument lengths is different.
\end{newer}

\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{lisp}
(map 'list \#'- '(1 2 3 4)) \EV\ (-1 -2 -3 -4) \\
(map 'string \\
~~~~~\#'(lambda (x) (if (oddp x) \#{\Xbackslash}1 \#{\Xbackslash}0)) \\
~~~~~'(1 2 3 4)) \\
~~~\EV\ "1010"
\end{lisp}
\end{defun}


\begin{defun}[Функция]
map-into result-sequence function &rest sequences

Функция \cdf{map-into} вычисляет последовательность с помощью применения функции
\emph{function} к соответствующим элементам исходных последовательностей и
помещает результат в последовательность \emph{result-sequence}.
Функция возвращается \emph{result-sequence}.

Аргументы \emph{result-sequence} и все \emph{sequences} должны быть списками
или векторами (одномерными массивами).
Функция \emph{function} должна принимать столько аргументов, сколько было
указано исходных последовательностей.
Если \emph{result-sequence} и другие аргументы \emph{sequences} не одинаковой
длины, цикл закончится на самой короткой последовательности. Если
\emph{result-sequence} является вектором с указателем заполнения, то этот
указатель во время цикла игнорируется, а после завершения устанавливается на то
количество элементов, которые были получены от функции \emph{function}.

Если функция \emph{function} имеет побочные эффекты, она может рассчитывать на
то, что сначала будет вызвана со всеми элементами в \cd{0}-ой позиции, затем со
всеми в \cd{1}-ой и так далее.

Функция \cdf{map-into} отличается от \cdf{map} тем, что модифицирует уже
имеющуюся последовательность, а не создаёт новую. Кроме того, \cdf{map-into}
может быть вызвана только с двумя аргументами (\emph{result-sequence} и
\emph{function}), тогда как \cdf{map} требует как минимум три параметра.

Если \emph{result-sequence} является \cdf{nil}, \cdf{map-into} немедленно
возвращает \cdf{nil}, потому что длина \cdf{nil} последовательности равняется
нулю.
\end{defun}


\begin{defun}[Функция]
some predicate sequence &rest more-sequences \\
every predicate sequence &rest more-sequences \\
notany predicate sequence &rest more-sequences \\
notevery predicate sequence &rest more-sequences

Всё это предикаты.
Функция \emph{predicate} должна принимать столько аргументов, сколько было
указано последовательностей. Функция \emph{predicate} сначала применяется к
элементам \cd{0}-ой позиции, затем, возможно, к элементам \cd{1}-ой позиции, и
так далее, до тех пор пока не сработает условие завершения цикла или не
закончится одна из последовательностей \emph{sequences}.

Если \emph{predicate} имеет побочные эффекты, он может рассчитывать на
то, что сначала будет вызвана со всеми элементами в \cd{0}-ой позиции, затем со 
всеми в \cd{1}-ой и так далее.

\cdf{some} завершается, как только применение \emph{predicate} вернёт не-{\false}
значение. Тогда \cdf{some} возвращает значение, на котором произошла остановка.
Если цикл достиг конца последовательности и ни одно применение \emph{predicate}
не вернуло не-{\false}, тогда возвращается значение {\false}.
Таким образом, можно сказать, что предикат \cdf{some} истинен, если
\emph{какой-либо (some)} вызов \emph{predicate} истинен.

\cdf{every} возвращает {\false}, как только применение \emph{predicate}
возвращает {\false}.
Если цикл достиг конца последовательности, \cdf{every} возвращает не-{\false}.
Таким образом, можно сказать, что предикат \cdf{every} истинен, если
\emph{каждый (every)} вызов \emph{predicate} истинен.

\cdf{notany} возвращает {\false}, как только применение \emph{predicate} 
возвращает не-{\false}.
Если цикл достиг конца последовательности, \cdf{notany} возвращает не-{\false}.
Таким образом, можно сказать, что предикат \cdf{notany} истинен, если
\emph{ни какой (notany)} вызов \emph{predicate} не истинен.

\cdf{notevery} возвращает не-{\false}, как только применение \emph{predicate} 
возвращает {\false}.
Если цикл достиг конца последовательности, \cdf{notevery} возвращает {\false}.
Таким образом, можно сказать, что предикат \cdf{notevery} истинен, если
\emph{ни каждый (notany)} вызов \emph{predicate} истинен.

\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}[Функция]
reduce function sequence &key :from-end :start :end :initial-value

Функция \cdf{reduce} объединяет все элементы последовательности использую
заданную (бинарную binary) операцию. Например \cdf{+} может суммировать все
элементы последовательности.

Указанная подпоследовательность последовательности \emph{sequence} объединяется
или <<редуцируется>> с помощью функции \emph{function}, которая должна принимать
два аргумента. Приведение (редуцирование, объединение) является
левоассоциативным, если только \cd{:from-end} не содержит истину, в последнем
случае операция становиться правоассоциативной. По-умолчанию
\cd{:from-end} равно {\nil}.
Если задан аргумент \cd{:initial-value}, то он логически помещается перед
подпоследовательностью (или после в случае истинности \cd{:from-end}) и
включается в операцию редуцирования.

Если указанная подпоследовательность содержит только один элемент и параметр
\cd{:initial-value} не задан, тогда этот элемент возвращается, и функция
\emph{function} ни разу не вызывается.
Если заданная подпоследовательность пуста, и задан параметр \cd{:initial-value},
тогда возвращается \cd{:initial-value}, и функция \emph{function} не вызывается.

Если заданная подпоследовательность пуста, и параметр \cd{:initial-value} не задан,
тогда функция \emph{function} вызывается без аргументов, и \cdf{reduce}
возвращает то, что вернула эта функция. Это единственное исключение из правила о
том, что функция \emph{function} вызывается с двумя аргументами.

\begin{lisp}
(reduce \#'+ '(1 2 3 4)) \EV\ 10 \\
(reduce \#'- '(1 2 3 4)) \EQ\ (- (- (- 1 2) 3) 4) \EV\ -8 \\
(reduce \#'- '(1 2 3 4) :from-end t)~~~~~;\textrm{Альтернативная сумма} \\
~~~\EQ\ (- 1 (- 2 (- 3 4))) \EV\ -2 \\
(reduce \#'+ '()) \EV\ 0 \\
(reduce \#'+ '(3)) \EV\ 3 \\
(reduce \#'+ '(foo)) \EV\ foo \\
(reduce \#'list '(1 2 3 4)) \EV\ (((1 2) 3) 4) \\
(reduce \#'list '(1 2 3 4) :from-end t) \EV\ (1 (2 (3 4))) \\
(reduce \#'list '(1 2 3 4) :initial-value 'foo) \\
~~~\EV\ ((((foo 1) 2) 3) 4) \\
(reduce \#'list '(1 2 3 4) \\
~~~~~~~~:from-end t :initial-value 'foo) \\
~~~\EV\ (1 (2 (3 (4 foo))))
\end{lisp}
Если функция \emph{function} имеет побочные эффекта, можно положится на порядок
вызовов функции так, как было продемонстрировано выше.

Имя <<reduce>> было позаимствовано из {APL}.

\begin{new}
X3J13 voted in March 1988 \issue{REDUCE-ARGUMENT-EXTRACTION}
to extend the \cdf{reduce} function to take
an additional keyword argument named \cd{:key}.  As usual, this argument
defaults to the identity function.  The value of this argument must be
a function that accepts at least one argument.  This function is applied once
to each element of the
sequence that is to participate in the reduction operation, in the order
implied by the \cd{:from-end} argument; the values returned by this
function are combined by the reduction \emph{function}.
However, the \cd{:key} function is \emph{not} applied
to the \cd{:initial-value} argument (if any).
\end{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}

\section{Модификация последовательностей}

Каждая из этих функций или модифицирует последовательность, или возвращает
модифицированную копию.

\begin{defun}[Функция]
fill sequence item &key :start :end

Функция модифицирует последовательность, заменяя каждый элемент
подпоследовательности, обозначенной с помощью параметров \cd{:start} и
\cd{:end}, объектом \emph{item}. \emph{item} может быть любым Lisp'овыми 
объектом, подходящим для типа элементов последовательности \emph{sequence}. 
Объект \emph{item} сохраняется в всех указанных компонентах
последовательности \emph{sequence}, начиная с позиции \cd{:start} (по-умолчанию
равна 0) и заканчивая невключительно позицией \cd{:end} (по-умолчанию равна
длине последовательности). \cd{fill} возвращает изменённую последовательность.
Например:
\begin{lisp}
(setq x (vector 'a 'b 'c 'd 'e)) \EV\ \#(a b c d e) \\
(fill x 'z \cd{:start} 1 \cd{:end} 3) \EV\ \#(a z z d e) \\
~~\textrm{and now} x \EV\ \#(a z z d e) \\
(fill x 'p) \EV\ \#(p p p p p) \\
~~\textrm{and now} x \EV\ \#(p p p p p)
\end{lisp}
\end{defun}

\begin{defun}[Функция]
replace sequence1 sequence2 &key :start1 :end1 :start2~:end2

Функция модифицирует последовательность \emph{sequence1} копируя в неё элементы
из последовательности \emph{sequence2}. Элементы \emph{sequence2} должны
принадлежать типу элементов \emph{sequence1}. Подпоследовательность
\emph{sequence2}, указанная с помощью параметров \cd{:start2} и \cd{:end2},
копируется в подпоследовательность \emph{sequence2}, указанную с помощью
параметров \cd{:start1} и \cd{:end1}. Аргументы \cd{:start1} и \cd{:start2}
по-умолчанию равны нулю. Аргументы \cd{:end1} и \cd{:end2} по-умолчанию
{\false}, что означает длины соответствующих последовательностей.
Если указанные подпоследовательности имеют не равные длины, тогда для наиболее
короткая из них определяет копируемые элементы. Лишние элементы
последовательностей функцией не обрабатываются.
Количество копируемых элементов можно вычислить так:
\begin{lisp}
(min (- \emph{end1} \emph{start1}) (- \emph{end2} \emph{start2}))
\end{lisp}
Значением функции \cdf{replace} является модифицированная последовательность
\emph{sequence1}.

Если обе последовательности равны (\cdf{eq}), и интервал для модификации
перекрывается с исходным интервалом, тогда поведение такое, как если бы все
исходные данные сохранялись во временном месте, а затем сохранялись в итоговый
интервал.
Однако, если последовательности не равны, но итоговый интервал пересекается с
исходным (возможно, при использовании \emph{соединённых} массивов), тогда
после выполнения \cdf{replace}, итоговое содержимое не определено.
\end{defun}

\begin{defun}[Функция]
remove item sequence &key :from-end :test :test-not :start :end :count :key \\
remove-if predicate sequence &key :from-end :start :end :count :key \\
remove-if-not predicate sequence &key :from-end :start :end :count :key

Результатом является последовательность того же типа, что и последовательность
\emph{sequence}. Однако, итоговая последовательность не будет содержать элементы
в интервале \cd{:start}-\cd{:end}, которые удовлетворяли условию.
Результат является копией входящей последовательности \emph{sequence} без
исключённых элементов. Неудалённые элементы сохраняются в таком же порядке.

Если указан аргумент \cd{:count}, то удаляться будет только это количество. Если
количество удаляемых элементов превышает параметр, тогда будут удалены только
самые левые в количестве равном \cd{:count}.

\begin{new}
X3J13 voted in January 1989
\issue{RANGE-OF-COUNT-KEYWORD}
to clarify that the \cd{:count} argument must be either \cdf{nil}
or an integer, and that supplying a negative integer produces the
same behavior as supplying zero.
\end{new}

Если при использовании \cd{:count} для параметра
\cd{:from-end} указано не-{\false} значение, тогда удаление элементов будет
происходить справа в количестве \cd{:count}.
Например:
\begin{lisp}
(remove 4 '(1 2 4 1 3 4 5)) \EV\ (1 2 1 3 5) \\
(remove 4 '(1 2 4 1 3 4 5) \cd{:count} 1) \EV\ (1 2 1 3 4 5) \\
(remove 4 '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 5) \\
(remove 3 '(1 2 4 1 3 4 5) \cd{:test} \#'>) \EV\ (4 3 4 5) \\
(remove-if \#'oddp '(1 2 4 1 3 4 5)) \EV\ (2 4 4) \\
(remove-if \#'evenp '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 5)
\end{lisp}
Результат \cdf{remove} может быть \emph{соединён} с исходной
последовательностью. Также результат может быть равен \cdf{eq} исходной
последовательности, если ни одного элементы не было удалено.

\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}[Функция]
delete item sequence &key :from-end :test :test-not :start~:end~:count~:key \\
delete-if predicate sequence &key :from-end :start~:end~:count~:key \\
delete-if-not predicate sequence &key :from-end :start~:end~:count~:key

Данная функция в отличие от \cdf{remove} модифицирует исходную
последовательность. Результатом является последовательность того же типа, что и последовательность
\emph{sequence}. Однако, итоговая последовательность не будет содержать элементы
в интервале \cd{:start}-\cd{:end}, которые удовлетворяли условию.
Результат является копией входящей последовательности \emph{sequence} без
исключённых элементов. Неудалённые элементы сохраняются в таком же порядке.
Последовательность \emph{sequence} может быть модифицирована, поэтому результат
может быть равен \cdf{eq} или нет исходной последовательности.

Если указан аргумент \cd{:count}, то удаляться будет только это количество. Если
количество удаляемых элементов превышает параметр, тогда будут удалены только
самые левые в количестве равном \cd{:count}.

\begin{new}
X3J13 voted in January 1989
\issue{RANGE-OF-COUNT-KEYWORD}
to clarify that the \cd{:count} argument must be either \cdf{nil}
or an integer, and that supplying a negative integer produces the
same behavior as supplying zero.
\end{new}

Если при использовании \cd{:count} для параметра
\cd{:from-end} указано не-{\false} значение, тогда удаление элементов будет
происходить справа в количестве \cd{:count}.
Например:
\begin{lisp}
(delete 4 '(1 2 4 1 3 4 5)) \EV\ (1 2 1 3 5) \\
(delete 4 '(1 2 4 1 3 4 5) \cd{:count} 1) \EV\ (1 2 1 3 4 5) \\
(delete 4 '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 5) \\
(delete 3 '(1 2 4 1 3 4 5) \cd{:test} \#'>) \EV\ (4 3 4 5) \\
(delete-if \#'oddp '(1 2 4 1 3 4 5)) \EV\ (2 4 4) \\
(delete-if \#'evenp '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 5)
\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}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations.
When the \emph{sequence} is a list,
\cdf{delete} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of that list.
When the \emph{sequence} is an array,
\cdf{delete} is permitted to alter the dimensions of the given array
and to slide some of its elements into new positions without permuting them
in order to produce the resulting array.

Furthermore, \cd{(delete-if \emph{predicate} \emph{sequence}~...)}
is required to behave exactly like
\begin{lisp}
(delete nil \emph{sequence} \\*
~~~~~~~~:test \#'(lambda (unused item) \\*
~~~~~~~~~~~~~~~~~~~(declare (ignore unused)) \\*
~~~~~~~~~~~~~~~~~~~(funcall \emph{predicate} item)) \\*
~~~~~~~~...)
\end{lisp}
\end{newer}
\end{defun}

\begin{defun}[Функция]
remove-duplicates sequence &key :from-end :test :test-not :start :end :key \\
delete-duplicates sequence &key :from-end :test :test-not :start :end :key

Функция попарно сравнивает элементы последовательности \emph{sequence}, и если
они равны, тогда первый из них удаляется (если параметр \cd{:from-end} равен
истине, то удаляется последний).
Результат является последовательностью того же типа, что и исходная, с
удалёнными повторяющимися элементами. Порядок следования элементов в итоге такой
же как в исходной последовательности.

\cdf{remove-duplicates} является не модифицирующей версией этой операции.
Результат \cdf{remove-duplicates} может быть \emph{соединён} с исходной
последовательностью. Также результат может быть равен \cdf{eq} исходной
последовательности, если ни одного элементы не было удалено.

\cdf{delete-duplicates} может модифицировать аргумент \emph{sequence}.

Например:
\begin{lisp}
(remove-duplicates '(a b c b d d e)) \EV\ (a c b d e) \\
(remove-duplicates '(a b c b d d e) \cd{:from-end} t) \EV\ (a b c d e) \\
(remove-duplicates '((foo \#{\Xbackslash}a) (bar \#{\Xbackslash}\%) (baz \#{\Xbackslash}A)) \\
~~~~~~~~~~~~~~~~~~~\cd{:test} \#'char-equal \cd{:key} \#'cadr) \\
~~~\EV\ ((bar \#{\Xbackslash}\%) (baz \#{\Xbackslash}A)) \\
(remove-duplicates '((foo \#{\Xbackslash}a) (bar \#{\Xbackslash}\%) (baz \#{\Xbackslash}A)) \\
~~~~~~~~~~~~~~~~~~~\cd{:test} \#'char-equal \cd{:key} \#'cadr \cd{:from-end} t) \\
~~~\EV\ ((foo \#{\Xbackslash}a) (bar \#{\Xbackslash}\%))
\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}

\begin{newer}
X3J13 voted in March 1989 \issue{REMF-DESTRUCTION-UNSPECIFIED}
to clarify the permissible side effects of certain operations.
When the \emph{sequence} is a list,
\cdf{delete-duplicates} is permitted to perform a \cdf{setf} on any part,
\emph{car} or \emph{cdr}, of the top-level list structure of that list.
When the \emph{sequence} is an array,
\cdf{delete-duplicates} is permitted to alter the dimensions of the given array
and to slide some of its elements into new positions without permuting them
in order to produce the resulting array.
\end{newer}
\end{defun}

\begin{defun}[Функция]
substitute newitem olditem sequence &key :from-end :test :test-not :start :end :count :key \\
substitute-if newitem test sequence &key :from-end :start~:end :count :key \\
substitute-if-not newitem test sequence &key :from-end :start :end :count :key

Результатом является последовательность такого же типа что и исходная
\emph{sequence}
за исключением того, что удовлетворяющие условию элементы в интервале
\cd{:start}-\cd{:end} будут заменены на объект \emph{newitem}. Эта операция
создаёт копию исходной последовательности с некоторыми изменёнными элементами.

Если указан аргумент \cd{:count}, то изменяться будет только это количество
элементов. Если 
количество изменяемых элементов превышает параметр, тогда будут удалены только
самые левые в количестве равном \cd{:count}.

\begin{new}
X3J13 voted in January 1989
\issue{RANGE-OF-COUNT-KEYWORD}
to clarify that the \cd{:count} argument must be either \cdf{nil}
or an integer, and that supplying a negative integer produces the
same behavior as supplying zero.
\end{new}

Если при использовании \cd{:count} для параметра
\cd{:from-end} указано не-{\false} значение, тогда изменение элементов будет
происходить справа в количестве \cd{:count}.
Например:
\begin{lisp}
(substitute 9 4 '(1 2 4 1 3 4 5)) \EV\ (1 2 9 1 3 9 5) \\
(substitute 9 4 '(1 2 4 1 3 4 5) \cd{:count} 1) \EV\ (1 2 9 1 3 4 5) \\
(substitute 9 4 '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 9 5) \\
(substitute 9 3 '(1 2 4 1 3 4 5) \cd{:test} \#'>) \EV\ (9 9 4 9 3 4 5) \\
(substitute-if 9 \#'oddp '(1 2 4 1 3 4 5)) \EV\ (9 2 4 9 9 4 9) \\
(substitute-if 9 \#'evenp '(1 2 4 1 3 4 5) \cd{:count} 1 \cd{:from-end} t) \\
~~~\EV\ (1 2 4 1 3 9 5)
\end{lisp}
Результат \cdf{substitute} может быть \emph{соединён} с исходной
последовательностью. Также результат может быть равен \cdf{eq} исходной
последовательности, если ни одного элементы не было изменено.

Смотрите также \cdf{subst}, которая осуществляет замену в древовидной структуре.

\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}[Функция]
nsubstitute newitem olditem sequence &key :from-end :test :test-not :start :end :count :key \\
nsubstitute-if newitem test sequence &key :from-end :start~:end :count :key \\
nsubstitute-if-not newitem test sequence &key :from-end :start :end :count :key

Эта функция является деструктивным аналогом для \cdf{substitute}. Это значит,
что они модифицирует свой аргумент.
Результатом является последовательность такого же типа что и исходная
\emph{sequence}
за исключением того, что удовлетворяющие условию элементы в интервале
\cd{:start}-\cd{:end} будут заменены на объект \emph{newitem}.
Последовательность \emph{sequence} может быть модифицирована, поэтому результат
может быть равен \cdf{eq} или нет исходной последовательности.

Смотрите также \cdf{nsubst}, которая осуществляет деструктивную замену в
древовидной структуре.

\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.
When the \emph{sequence} is a list,
\cdf{nsubstitute} or \cdf{nsubstitute-if}
is required to perform a \cdf{setf} on any
\emph{car} of the top-level list structure of that list
whose old contents must be replaced with \emph{newitem}
but is forbidden to perform a \cdf{setf} on any \cdf{cdr} of the list.
When the \emph{sequence} is an array,
\cdf{nsubstitute} or \cdf{nsubstitute-if}
is required to perform a \cdf{setf} on any element of the array
whose old contents must be replaced with \emph{newitem}.
These functions, therefore, may successfully be
used solely for effect, the caller discarding the returned value
(though some programmers find this stylistically distasteful).
\end{newer}
\end{defun}

\section{Поиск элементов последовательностей}

Каждая из этих функций ищет в последовательности элемент, удовлетворяющий
некоторому условию.

\begin{defun}[Функция]
find item sequence &key :from-end :test :test-not :start~:end :key \\
find-if predicate sequence &key :from-end :start :end :key \\
find-if-not predicate sequence &key :from-end :start~:end~:key

Если последовательность \emph{sequence} содержит элемент, удовлетворяющий
условию, тогда возвращается первый найденный слева элемент, иначе возвращается
{\false}.

Если заданы параметры \cd{:start} и \cd{:end}, тогда поиск осуществляется в этом
интервале.

Если \cd{:from-end} указан в не-{\false}, тогда результатом функции будет
найденный элемент справа.

\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}[Функция]
position item sequence &key :from-end :test :test-not :start~:end~:key \\
position-if predicate sequence &key :from-end :start~:end~:key \\
position-if-not predicate sequence &key :from-end :start~:end~:key

Если последовательность \emph{sequence} содержит элемент, удовлетворяющий
условию, тогда возвращается позиция найденного элемента слева, иначе возвращается
{\false}.

Если заданы параметры \cd{:start} и \cd{:end}, тогда поиск осуществляется в этом
интервале. Однако возвращаемый индекс будет относиться ко всей
последовательности в целом.

Если \cd{:from-end} указан в не-{\false}, тогда результатом функции будет
индекс найденного элемент справа. (Однако, возвращаемый индекс, будет, как
обычно, принадлежать нумерации слева направо.)

\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}

Ниже приведены несколько примеров использования нескольких функций,
преимущественно \cdf{position-if} и \cdf{find-if}, для обработки строк.
Также используется \cdf{loop}.
\begin{lisp}
(defun debug-palindrome (s) \\*
~~(flet ((match (x) (char-equal (first x) (third x)))) \\*
~~~~(let* ((pairs (loop for c across s \\*
~~~~~~~~~~~~~~~~~~~~~~~~for j from 0 \\*
~~~~~~~~~~~~~~~~~~~~~~~~when (alpha-char-p c) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~collect (list c j))) \\*
~~~~~~~~~~~(quads (mapcar \#'append pairs (reverse pairs))) \\*
~~~~~~~~~~~(diffpos (position-if (complement \#'match) quads))) \\
~~~~~~(when diffpos \\*
~~~~~~~~(let* ((diff (elt quads diffpos)) \\*
~~~~~~~~~~~~~~~(same (find-if \#'match quads \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~:start (+ diffpos 1)))) \\
~~~~~~~~~~(if same \\*
~~~~~~~~~~~~~~(format nil \\*
~~~~~~~~~~~~~~~~~~~~~~"/{\Xtilde}A/ (at {\Xtilde}D) is not the reverse of /{\Xtilde}A/" \\*
~~~~~~~~~~~~~~~~~~~~~~(subseq s (second diff) (second same)) \\*
~~~~~~~~~~~~~~~~~~~~~~(second diff) \\*
~~~~~~~~~~~~~~~~~~~~~~(subseq s (+ (fourth same) 1) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(+ (fourth diff) 1))) \\*
~~~~~~~~~~~~~~"This palindrome is completely messed up!"))))))
\end{lisp}
Вот пример поведения этой функции
\begin{lisp}
(setq panama~~~~~;\textrm{Предполагаемый палиндром?} \\*
~~~~~~"A man, a plan, a canoe, pasta, heros, rajahs, \\*
~~~~~~~a coloratura, maps, waste, percale, macaroni, a gag, \\*
~~~~~~~a banana bag, a tan, a tag, a banana bag again \\*
~~~~~~~(or a camel), a crepe, pins, Spam, a rut, a Rolo, \\*
~~~~~~~cash, a jar, sore hats, a peon, a canal--Panama!")
\end{lisp}
\begin{lisp}
(debug-palindrome panama) \\*
~~\EV\ "/wast/ (at 73) is not the reverse of /, pins/" \\
\\
(replace panama "snipe" :start1 73)~~~~~;\textrm{Восстановить} \\*
~~\EV\ "A man, a plan, a canoe, pasta, heros, rajahs, \\*
~~~~~~~a coloratura, maps, snipe, percale, macaroni, a gag, \\*
~~~~~~~a banana bag, a tan, a tag, a banana bag again \\*
~~~~~~~(or a camel), a crepe, pins, Spam, a rut, a Rolo, \\*
~~~~~~~cash, a jar, sore hats, a peon, a canal--Panama!" \\
\\
(debug-palindrome panama) \EV\ nil~~~~~;\textrm{Первоклассный---истинный палиндром} \\
\\
(debug-palindrome "Rubber baby buggy bumpers") \\*
~~\EV\ "/Rubber / (at 0) is not the reverse of /umpers/" \\
\\
(debug-palindrome "Common Lisp: The Language") \\*
~~\EV\ "/Commo/ (at 0) is not the reverse of /guage/" \\
\\
(debug-palindrome "Complete mismatches are hard to find") \\*
~~\EV\ \\
~~"/Complete mism/ (at 0) is not the reverse of /re hard to find/" \\
\\
(debug-palindrome "Waltz, nymph, for quick jigs vex Bud") \\*
~~\EV\ "This palindrome is completely messed up!" \\
\\
(debug-palindrome "Doc, note: I dissent.~~A fast never \\*
~~~~~~~~~~~~~~~~~~~prevents a fatness.~~I diet on cod.") \\*
~~\EV\nil~~~~~;\textrm{Другой победитель} \\
\\
(debug-palindrome "Top step's pup's pet spot") \EV\ nil
\end{lisp}

\begin{defun}[Функция]
count item sequence &key :from-end :test :test-not :start~:end~:key \\
count-if predicate sequence &key :from-end :start~:end~:key \\
count-if-not predicate sequence &key :from-end :start~:end~:key

Результатом является неотрицательное целое число, указывающее на количество
элементов из указанной подпоследовательности, удовлетворяющих условию.

\cd{:from-end} не оказывает никакого воздействия, и оставлен только для
совместимости с другими функциями.

\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}[Функция]
mismatch sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2

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

Если параметр \cd{:from-end} равен не-{\false} значению, тогда возвращается
увеличенная на 1 позиция первого не совпавшего элемента справа. Фактически,
(под)последовательности выравниваются по своим правым концам, затем сравниваются
последние элементы, затем предпоследние и так далее. Возвращаемый индекс
принадлежит первой последовательности \emph{sequence1}.

\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}[Функция]
search sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2

Функция осуществляет поэлементный поиск последовательности \emph{sequence1} в
последовательности \emph{sequence1}.
Если поиск не увенчался успехом, результатом является значение {\false}. Иначе,
результат является индексом первого совпавшего элемента слева во второй
последовательности \emph{sequence2}.

Если аргумент \cd{:from-end} равен не-{\false}, поиск осуществляется справа, и
результат является индексом элемента слева в первой совпавшей
подпоследовательности справа.

Реализация может выбирать алгоритм поиска на своё усмотрение. Количество
проводимых сравнений не может быть указано точно.
Например, \cdf{search} при \cd{:from-end} равном не-{\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}

\section{Сортировка и слияние}

Эти функции могут модифицировать исходные данные:
сортировать или соединять две уже отсортированные последовательности.

\begin{defun}[Функция]
sort sequence predicate &key :key \\
stable-sort sequence predicate &key :key

Функция сортирует последовательность \emph{sequence} в порядке, определяемом
предикатом \emph{predicate}. Результат помещается в исходную
последовательность. Предикат \emph{predicate} должен принимать два аргумента,
возвращать не-{\false} тогда и только тогда, когда первый аргумент строго меньше
второго (в подходящем для этого смысле).
Если первый аргумент больше или равен второму (в подходящем для этого смысле),
тогда предикат \emph{predicate} должен вернуть {\false}.

Функция \cdf{sort} устанавливает отношение между двумя элементами с помощью
предиката \emph{predicate}, применённого к извлечённой из элемента ключевой
части. Функция \cd{:key}, применённая к элементу, должна возвращать его ключевую
часть.
Аргумент \cd{:key} по-умолчанию равен функции эквивалентности, тем самым
возвращая весь элемент.

Функция \cd{:key} не должна иметь побочных эффектов.
Полезным примером функции \cd{:key} может быть функция-селектор для некоторой
структуры (созданной с помощью \cdf{defstruct}), используемая для сортировки
последовательности структур.
\begin{lisp}
(sort \emph{a} \emph{p} \cd{:key} \emph{s})
   \EQ\ (sort \emph{a} \#'(lambda (x y) (\emph{p} (\emph{s} x) (\emph{s} y))))
\end{lisp}
Тогда как оба выражения эквивалентны, для некоторых реализаций и определённых
типов первое выражение может оказаться эффективнее.
Например, реализация может выбрать сначала вычислить все ключевые части,
поместить их в таблицу, а затем параллельно сортировать таблицы.

Если функции \cd{:key} и \emph{predicate} всегда возвращают управление, тогда
операция сортировки будет всегда возвращать последовательность, содержащую такое
же количество элементов как и в исходной (результат является просто
последовательностью с переставленными элементами).
Это поведение гарантируется, даже если предикат \emph{predicate} в
действительности не производит сравнение (в таком случае элементы будут
расположены в неопределённом порядке, но ни один из них не будет потерян). Если
функция \cd{:key} последовательно возвращает необходимые ключевые части, и
\emph{predicate} отображает некоторый критерий для упорядочивания данных частей,
тогда элементы итоговой последовательности будут корректно отсортированы в
соответствие с этим критерием.

Операция сортировки, выполняемая с помощью \cdf{sort}, не гарантированно
\emph{постоянна}.
Элементы, рассматриваемые предикатом \emph{predicate} как равные, могут остаться
или нет в оригинальном порядке.
(Предполагается, что \emph{predicate} рассматривает два элемента \emph{x} и
\emph{y} равными, если 
\cd{(funcall \emph{predicate} \emph{x} \emph{y})} и
\cd{(funcall \emph{predicate} \emph{y} \emph{x})} являются ложными.)
Функция \cdf{stable-sort} гарантирует постоянность, но в некоторых ситуациях
может быть медленнее чем \cdf{sort}.

Операция сортировки может быть деструктивное во всех случаях. В случае аргумента
массива, она производится перестановкой элементов.
В случае аргумента списка, список деструктивно переупорядочивается похожим
образом как в \cdf{nreverse}.
Таким образом, если аргумент не должен быть изменён, пользователь должен
сортировать копию исходной последовательности.

Если применение функций \cd{:key} или \emph{predicate} вызывает ошибку, то
состояние сортируемого массива или списка не определено.
Однако, если ошибка может быть исправлена, сортировка, конечно же, будет
завершена корректно.

Следует отметить, что сортировка требует много сравнений и следовательно много
вызовов предиката \emph{predicate}, сортировка будет более быстрой, если
\emph{predicate} является компилируемой, а не интерпретируемой функцией.

Например:
\begin{lisp}
(setq foovector (sort foovector \#'string-lessp \cd{:key} \#'car))
\end{lisp}
Если \cdf{foovector} содержит эти данные перед сортировкой
\begin{lisp}
("Tokens" "The Lion Sleeps Tonight") \\
("Carpenters" "Close to You") \\
("Rolling Stones" "Brown Sugar") \\
("Beach Boys" "I Get Around") \\
("Mozart" "Eine Kleine Nachtmusik" (K 525)) \\
("Beatles" "I Want to Hold Your Hand")
\end{lisp}
тогда после неё, \cdf{foovector} будет содержать
\begin{lisp}
("Beach Boys" "I Get Around") \\
("Beatles" "I Want to Hold Your Hand") \\
("Carpenters" "Close to You") \\
("Mozart" "Eine Kleine Nachtmusik" (K 525)) \\
("Rolling Stones" "Brown Sugar") \\
("Tokens" "The Lion Sleeps Tonight")
\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}[Функция]
merge result-type sequence1 sequence2 predicate &key :key

Функция деструктивно соединяет две последовательности \emph{sequence1} и
\emph{sequence2} в порядке определяемом предикатом \emph{predicate}.
Результат является последовательностью типа \emph{result-type}, который должен
быть подтипом \cdf{sequence}.
Предикат \emph{predicate} должен принимать два аргумента,
возвращать не-{\false} тогда и только тогда, когда первый аргумент строго меньше
второго (в подходящем для этого смысле).
Если первый аргумент больше или равен второму (в подходящем для этого смысле),
тогда предикат \emph{predicate} должен вернуть {\false}.

Функция \cdf{merge} устанавливает отношение между двумя элементами с помощью
предиката \emph{predicate}, применённого к извлечённой из элемента ключевой
части. Функция \cd{:key}, применённая к элементу, должна возвращать его ключевую
часть.
Аргумент \cd{:key} по-умолчанию равен функции эквивалентности, тем самым
возвращая весь элемент.

Функция \cd{:key} не должна иметь побочных эффектов.
Полезным примером функции \cd{:key} может быть функция-селектор для некоторой
структуры (созданной с помощью \cdf{defstruct}), используемая для сортировки
последовательности структур.

Если функции \cd{:key} и \emph{predicate} всегда возвращают управление, тогда
операция сортировки будет всегда завершаться.
Результатом слияния двух последовательностей \emph{x} и \emph{y} является новая
последовательность \emph{z}, у которой длина равняется сумма длин \emph{x} и
\emph{y}. \emph{z} содержит все элементы \emph{x} и \emph{y}.
Если \emph{x1} и \emph{x2} являются элементами \emph{x}, и \emph{x1} стоит
прежде \emph{x2}, тогда в \emph{z} \emph{x1} также будет стоять прежде чем
\emph{x2}. Такое же правило и для \emph{y}. Если коротко, \emph{z} является
\emph{слиянием} \emph{x} и \emph{y}.

Более того, если \emph{x} и \emph{y} были правильно отсортированы в соответствие
с предикатом \emph{predicate}, тогда \emph{z} будет также правильно
отсортирована. Например,
\begin{lisp}
(merge 'list '(1 3 4 6 7) '(2 5 8) \#'<) \EV\ (1 2 3 4 5 6 7 8)
\end{lisp}
Если \emph{x} или \emph{y} не были отсортированы, тогда \emph{z} также не будет
отсортирована. Однако слияние в любом случае произойдёт.

Операция слияния гарантированно \emph{постоянна}.
Если два или более элементов рассматриваются предикатом \emph{predicate} как
равные, тогда в результате элементы из \emph{sequence1} будут предшествовать
элементам из \emph{sequence2}.
(Предполагается, что \emph{predicate} рассматривает два элемента \emph{x} и
\emph{y} равными, если 
\cd{(funcall \emph{predicate} \emph{x} \emph{y})} и
\cd{(funcall \emph{predicate} \emph{y} \emph{x})} являются ложными.)
Например:
\begin{lisp}
(merge 'string "BOY" "nosy" \#'char-lessp) \EV\ "BnOosYy"
\end{lisp}
Результат не может быть \cd{"BnoOsYy"}, \cd{"BnOosyY"} или \cd{"BnoOsyY"}.
Функция \cdf{char-lessp} игнорирует регистр, таким образом, например, символы \cd{Y} и
\cd{y} равны. Свойство постоянности гарантирует, что символ из первого аргумента
(\cd{Y}) должен предшествовать символу из второго аргумента (\cd{y}).

\begin{newer}
X3J13 voted in June 1989 \issue{SEQUENCE-TYPE-LENGTH} to specify that
\cdf{merge} should signal an error if the sequence type specifies the number of
elements and the sum of the lengths of the two sequence arguments is
different.
\end{newer}

\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