14. Sequences

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.

change_begin
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).
change_end

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        mismatch

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

change_begin
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.
change_end

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.

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

A ``start’’ argument must always be a non-negative integer and defaults to zero if not supplied; it is not permissible to pass nil as a ``start’’ argument.
An ``end’’ argument must be either a non-negative integer or nil (which indicates the end of the sequence) and defaults to nil if not supplied; therefore supplying nil is equivalent to not supplying such an argument.
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 length).
The default value for the ``end’’ argument is the active length of the corresponding sequence.
The ``start’’ value (after defaulting, if necessary) must not be greater than the corresponding ``end’’ value (after defaulting, if necessary).

This may be summarized as follows. Let x be the sequence within which indices are to be considered. Let s be the ``start’’ argument for that sequence of any standard function, whether explicitly specified or defaulted, through omission, to zero. Let e be the ``end’’ argument for that sequence of any standard function, whether explicitly specified or defaulted, through omission or an explicitly passed nil value, to the active length of x, as returned by length. Then it is an error if the test (<= 0se(lengthx)) is not true.
change_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:

A basic function was called, testfn was specified by the keyword :test, and (funcalltestfnitem(keyfnx)) is true.
A basic function was called, testfn was specified by the keyword :test-not, and (funcalltestfnitem(keyfnx)) is false.
An -if function was called, and (funcallpredicate(keyfnx)) is true.
An -if-not function was called, and (funcallpredicate(keyfnx)) is false.

In each case keyfn is the value of the :key keyword argument (the default being the identity function). See, for example, remove.

In the following function descriptions, two elements x and y taken from sequences ``match’’ if either of the following holds:

testfn was specified by the keyword :test, and (funcalltestfn(keyfnx) (keyfny)) is true.
testfn was specified by the keyword :test-not, and (funcalltestfn(keyfnx) (keyfny)) is false.

See, for example, search.

change_begin
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.
change_end

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.

change_begin
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]
complementfn

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))

Next: Simple Sequence Functions Up: Common Lisp the Language Previous: Character Control-Bit Functions

AI.Repository@cs.cmu.edu