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]
fillsequenceitem&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]
replacesequence1sequence2&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-ifpredicatesequence...) 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

AI.Repository@cs.cmu.edu