Common Lisp the Language, 2nd Edition

Next: Searching Sequences for Up: Sequences Previous: ConcatenatingMapping, and

# 14.3. Modifying Sequences

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

[Function]
`fill sequence item &key :start :end`

The sequence is destructively modified by replacing each element of the subsequence specified by the `:start` and `:end` parameters with the item. The item may be any Lisp object but must be a suitable element for the sequence. The item is stored into all specified components of the sequence, beginning at the one specified by the `:start` index (which defaults to zero), up to but not including the one specified by the `:end` index (which defaults to the length of the sequence). `fill` returns the modified sequence. For example:

    (setq x (vector 'a 'b 'c 'd 'e)) => #(a b c d e)
    (fill x 'z :start 1 :end 3) => #(a z z d e)
      and now x => #(a z z d e)
    (fill x 'p) => #(p p p p p)
      and now x => #(p p p p p)

[Function]
`replace sequence1 sequence2 &key :start1 :end1 :start2 :end2`

The sequence sequence1 is destructively modified by copying successive elements into it from sequence2. The elements of sequence2 must be of a type that may be stored into sequence1. The subsequence of sequence2 specified by `:start2` and `:end2` is copied into the subsequence of sequence1 specified by `:start1` and `:end1`. (The arguments `:start1` and `:start2` default to zero. The arguments `:end1` and `:end2` default to `nil`, 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:

    (min (- end1 start1) (- end2 start2))

The value returned by `replace` is the modified sequence1.

If sequence1 and sequence2 are the same (`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 sequence1 and sequence2 are 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 `replace` operation the subsequence of sequence1 being modified will have unpredictable contents.

[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 sequence that has the same elements except that those in the subsequence delimited by `:start` and `:end` and satisfying the test (see above) have been removed. This is a non-destructive operation; the result is a copy of the input 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 `:count` argument, if supplied, limits the number of elements removed; if more than `:count` elements satisfy the test, then of these elements only the leftmost are removed, as many as specified by `:count`.

X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD) to clarify that the `:count` argument must be either `nil` or an integer, and that supplying a negative integer produces the same behavior as supplying zero.

A non-`nil :from-end` specification matters only when the `:count` argument is provided; in that case only the rightmost `:count` elements satisfying the test are removed. For example:

    (remove 4 '(1 2 4 1 3 4 5)) => (1 2 1 3 5)
    (remove 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 1 3 4 5)
    (remove 4 '(1 2 4 1 3 4 5) :count 1 :from-end t)
       => (1 2 4 1 3 5)
    (remove 3 '(1 2 4 1 3 4 5) :test #'>) => (4 3 4 5)
    (remove-if #'oddp '(1 2 4 1 3 4 5)) => (2 4 4)
    (remove-if #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t)
       => (1 2 4 1 3 5)

The result of `remove` may share with the argument sequence; a list result may share a tail with an input list, and the result may be `eq` to the input sequence if no elements need to be removed.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

[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 `remove`. The result is a sequence of the same kind as the argument sequence that has the same elements except that those in the subsequence delimited by `:start` and `:end` and satisfying the test (see above) have been deleted. This is a destructive operation. The argument sequence may be destroyed and used to construct the result; however, the result may or may not be `eq` to sequence. Elements not deleted occur in the same order in the result as they did in the argument.

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

X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD) to clarify that the `:count` argument must be either `nil` or an integer, and that supplying a negative integer produces the same behavior as supplying zero.

A non-`nil :from-end` specification matters only when the `:count` argument is provided; in that case only the rightmost `:count` elements satisfying the test are deleted. For example:

    (delete 4 '(1 2 4 1 3 4 5)) => (1 2 1 3 5)
    (delete 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 1 3 4 5)
    (delete 4 '(1 2 4 1 3 4 5) :count 1 :from-end t)
       => (1 2 4 1 3 5)
    (delete 3 '(1 2 4 1 3 4 5) :test #'>) => (4 3 4 5)
    (delete-if #'oddp '(1 2 4 1 3 4 5)) => (2 4 4)
    (delete-if #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t)
       => (1 2 4 1 3 5)

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify the permissible side effects of certain operations. When the sequence is a list, `delete` is permitted to perform a `setf` on any part, car or cdr, of the top-level list structure of that list. When the sequence is an array, `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, `(delete-if predicate sequence ...)` is required to behave exactly like

    (delete nil sequence
            :test #'(lambda (unused item)
                       (declare (ignore unused))
                       (funcall predicate item))
            ...)

Compatibility note: In MacLisp, the `delete` function uses an `equal` comparison rather than `eql`, which is the default test for `delete` in Common Lisp. Where in MacLisp one would write `(delete x y)`, one must in Common Lisp write `(delete x y :test #'equal)` to get the completely identical effect. Similarly, one can get the precise effect, and no more, of the MacLisp `(delq x y)` by writing in Common Lisp `(delete x y :test #'eq)`.

[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 sequence are compared pairwise, and if any two match, then the one occurring earlier in the sequence is discarded (but if the `: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 sequence.

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

`delete-duplicates` may destroy the argument sequence.

Some examples:

    (remove-duplicates '(a b c b d d e)) => (a c b d e)
    (remove-duplicates '(a b c b d d e) :from-end t) => (a b c d e)
    (remove-duplicates '((foo #\a) (bar #\%) (baz #\A))
                       :test #'char-equal :key #'cadr)
       => ((bar #\%) (baz #\A))
    (remove-duplicates '((foo #\a) (bar #\%) (baz #\A))
                       :test #'char-equal :key #'cadr :from-end t)
       => ((foo #\a) (bar #\%))

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

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify the permissible side effects of certain operations. When the sequence is a list, `delete-duplicates` is permitted to perform a `setf` on any part, car or cdr, of the top-level list structure of that list. When the sequence is an array, `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.

[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 sequence that has the same elements except that those in the subsequence delimited by `:start` and `:end` and satisfying the test (see above) have been replaced by newitem. This is a non-destructive operation; the result is a copy of the input sequence, save that some elements are changed.

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

X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD) to clarify that the `:count` argument must be either `nil` or an integer, and that supplying a negative integer produces the same behavior as supplying zero.

A non-`nil :from-end` specification matters only when the `:count` argument is provided; in that case only the rightmost `:count` elements satisfying the test are replaced. For example:

    (substitute 9 4 '(1 2 4 1 3 4 5)) => (1 2 9 1 3 9 5)
    (substitute 9 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 9 1 3 4 5)
    (substitute 9 4 '(1 2 4 1 3 4 5) :count 1 :from-end t)
       => (1 2 4 1 3 9 5)
    (substitute 9 3 '(1 2 4 1 3 4 5) :test #'>) => (9 9 4 9 3 4 5)
    (substitute-if 9 #'oddp '(1 2 4 1 3 4 5)) => (9 2 4 9 9 4 9)
    (substitute-if 9 #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t)
       => (1 2 4 1 3 9 5)

The result of `substitute` may share with the argument sequence; a list result may share a tail with an input list, and the result may be `eq` to the input sequence if no elements need to be changed.

See also `subst`, which performs substitutions throughout a tree.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

[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 `substitute`. The result is a sequence of the same kind as the argument sequence that has the same elements except that those in the subsequence delimited by `:start` and `:end` and satisfying the test (see above) have been replaced by newitem. This is a destructive operation. The argument sequence may be destroyed and used to construct the result; however, the result may or may not be `eq` to sequence.

See also `nsubst`, which performs destructive substitutions throughout a tree.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

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

Next: Searching Sequences for Up: Sequences Previous: ConcatenatingMapping, and