Common Lisp the Language, 2nd Edition
The type 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 2).
elt reverse map remove length nreverse some remove-duplicates subseq concatenate every delete copy-seq position notany delete-duplicates fill find notevery substitute replace sort reduce nsubstitute count merge search mismatchSome 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 eql to that item. (A test other than eql can be specified by the :test or :test-not keyword. It is an error to use both of these keywords in the same call.) The variants formed by adding -if and -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,
(remove item sequence)
returns a copy of sequence from which all elements eql to item have been removed;
(remove item sequence :test #'equal)
returns a copy of sequence from which all elements equal to item have been removed;
(remove-if #'numberp sequence)
returns a copy of sequence from which all numbers have been removed.
If an operation tests elements of a sequence in any manner, the keyword argument :key, if not nil, 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 (assq item seq) could be obtained by
(find item sequence :test #'eq :key #'car)
This searches for the first element of sequence whose car is eq to item.
X3J13 voted in June 1988 (FUNCTION-TYPE) to allow the :key function
to be only of type symbol or function; a lambda-expression
is no longer acceptable as a functional argument. One must use the
function special form or the abbreviation #' before
a lambda-expression that appears as an explicit argument form.
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-nil value for the keyword argument :from-end. (The processing order specified by the :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 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 :start and :end. These arguments should be integer indices into the sequence, with startend (it is an error if start>end). They indicate the subsequence starting with and including element start and up to but excluding element end. The length of the subsequence is therefore end-start. If start is omitted, it defaults to zero; and if end is omitted or nil, it defaults to the length of the sequence. Therefore if both start and 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 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:
(position #\b "foobar" :start 2 :end 5) => 3 (position #\b (subseq "foobar" 2 5)) => 1
If two sequences are involved, then the keyword arguments :start1, :end1, :start2, and :end2 are used to specify separate subsequences for each sequence.
X3J13 voted in June 1988 (SUBSEQ-OUT-OF-BOUNDS)
(and further clarification was voted in January 1989
(RANGE-OF-START-AND-END-PARAMETERS) )
to specify that these rules apply not
only to all built-in functions that have keyword parameters named
:start, :start1, :start2, :end, :end1,
or :end2 but also to functions such as subseq
that take required or optional parameters that are documented
as being named start or end.
For some functions, notably remove and delete, the keyword argument :count is used to specify how many occurrences of the item should be affected. If this is nil or is not supplied, all matching items are affected.
In the following function descriptions, an element x of a sequence ``satisfies the test'' if any of the following holds:
In the following function descriptions, two elements x and y taken from sequences ``match'' if either of the following holds:
X3J13 voted in June 1988 (FUNCTION-TYPE) to allow the testfn
or predicate
to be only of type symbol or function; a lambda-expression
is no longer acceptable as a functional argument. One must use the
function special form or the abbreviation #' before
a lambda-expression that appears as an explicit argument form.
You may depend on the order in which arguments are given to testfn; this permits the use of non-commutative test functions in a predictable manner. The order of the arguments to 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 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 simple vector (see section 2.5). Similarly, any strings constructed will be simple strings.
X3J13 voted in January 1989
(TEST-NOT-IF-NOT)
to deprecate the use of :test-not keyword arguments
and -if-not functions. This means that these features are very
likely to be retained in the forthcoming standard but are regarded as
candidates for removal in a future revision of the ANSI standard.
X3J13 also voted in January 1989
(FUNCTION-COMPOSITION)
to add the complement function, intended to reduce or eliminate the
need for these deprecated features. Time will tell. I note that
many features in Fortran have been deprecated but very few indeed
have actually been removed or altered incompatibly.
[Function]
complement fn
Returns a function whose value is the same as that of not applied to the result of applying the function fn to the same arguments. One could define complement as follows:
(defun complement (fn)
#'(lambda (&rest arguments)
(not (apply fn arguments))))
One intended use of complement is to supplant the use of :test-not arguments and -if-not functions.
(remove-if-not #'virtuous senators) ==
(remove-if (complement #'virtuous) senators)
(remove-duplicates telephone-book
:test-not #'mismatch) ==
(remove-duplicates telephone-book
:test (complement #'mismatch))