Common Lisp the Language, 2nd Edition

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

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

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

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.

- 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 `(<= 0 s e (length x))` is not true.

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 `(funcall testfn item (keyfn x))` is true.

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

- An `-if` function was called, and `(funcall predicate (keyfn x))` is true.

- An `-if-not` function was called, and `(funcall predicate (keyfn x))` 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 `(funcall testfn (keyfn x) (keyfn y))` is true.

- testfn was specified by the keyword `:test-not`, and `(funcall testfn (keyfn x) (keyfn y))` is false.

See, for example, `search`.

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

- Simple Sequence Functions
- Concatenating, Mapping, and Reducing Sequences
- Modifying Sequences
- Searching Sequences for Items
- Sorting and Merging

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