Chapter 13 - Still More Things You Can Do with Sequences

In this chapter we'll meet the most useful sequence functions, and see how to use them. We'll also reprise earlier admonitions about proper use of destructive functions.

CONCATENATE: new sequences from old

CONCATENATE always creates a new sequence from (of course) the concatenation of zero or more argument sequences. You must specify the type of the result, and the argument types must be proper subtypes of the sequence type.

? (concatenate 'list) ; no argument sequences 
NIL
? (concatenate 'vector) ; no argument sequences 
#()
? (concatenate 'list '(1 2 3) (4 5))
(1 2 3 4 5)
? (concatenate 'vector #(1 2 3) #(4 5))
#(1 2 3 4 5)
? (concatenate 'list #(1 2 4) '(4 5))
(1 2 3 4 5)
? (concatenate 'vector '(1 2 3) #(4 5))
#(1 2 3 4 5)
? (concatenate 'list "hello") ; string is a subtype of sequence 
(#\h #\e #\l #\l #\o)

ELT and SUBSEQ get what you want from any sequence (also, COPY-SEQ)

If you need to pick out one element (or a range of elements) from a sequence, you can use ELT (to pick out one element) or SUBSEQ (to pick out a range of elements). But don't use these unless you're really sure you can't narrow down the sequence type to a vector or list; there are more specific (hence more efficient) accessors for the less general types.

SUBSEQ makes a copy of a specified portion of a sequence. COPY-SEQ is closely related to SUBSEQ, except that it copies all of the elements of a sequence.

? (elt '(1 2 3 4 5) 1) ; zero-based indexing 
2
? (subseq '(1 2 3 4 5) 2) ; 3rd element through end 
(3 4 5)
? (let ((l '(1 2 3 4 5)))
    (subseq l 2 (length l))) ; same effect as previous 
? (subseq '(1 2 3 4 5) 0 3) ; element at ending index is not copied 
(1 2 3)
? (subseq #(#\a #\b #\c #\d #\e) 2 4)
#(#\c #\d)
? (copy-seq '(a b c))
(A B C)

REVERSE turns a sequence end-for-end (also, NREVERSE)

REVERSE makes a copy of a sequence, with the order of elements reversed. NREVERSE is the destructive counterpart of REVERSE; it is more efficient, but it modifies its input argument.

REVERSE is commonly used in code similar to the following.

(defun collect-even-numbers (number-list)
  (let ((result ()))
    (dolist (number number-list)
      (when (evenp number)
        (push number result)))
    (nreverse result)))

The DOLIST and PUSH collect even numbers on the result list, but they are in the reverse order of their original positions on the input list. The final NREVERSE puts them back into their original order. This is a safe use of the destructive function NREVERSE because the RESULT variable can not be shared; it is forgotten as soon as control leaves the LET form.

LENGTH: size counts after all

There's not much to say about LENGTH. Just remember that for lists, LENGTH counts only the elements of the top-level list, and not those of any nested lists.

? (length '((1 2 3) (4 5) (6) 7 () 8 9))
7

COUNT: when it's what's inside that matters

If you find your program filters a sequence only to get the length of the result, use COUNT (and related functions COUNT-IF and COUNT-IF-NOT) instead.

? (count 3 '(1 3 3 4 2 5 9 8 3 1 9)) ; count occurrences 
3
? (count-if #'oddp '(1 3 3 4 2 5 9 8 3 1 9)) ; count matches to predicate 
8
? (count-if-not #'evenp '(1 3 3 4 2 5 9 8 3 1 9)) ; count mismatches using predicate 
8

These functions accept keyword arguments:

Keyword      Value                                        Default
-------      -----                                        -------
:START       starting index (inclusive)                   0
:END         ending index (exclusive)                     NIL
:FROM-END    non-NIL to work backwards from end element   NIL
:KEY         function to select match data from element   NIL

A NIL value for the :END keyword designates a position just past the end of the sequence; since this is an exclusive limit, the last element will be processed. (If you specified the index of the last element, the last element would not be processed.)

The :FROM-END keyword is useful in the case that the test function has side-effects, and the order of the side-effects is important.

When the :KEY argument is not NIL, it should be a function of one argument that extracts data from the sequence element. For example:

? (count 3 '((1 2 3) (2 3 1) (3 1 2) (2 1 3) (1 3 2) (3 2 1)) :key #'second)
2

COUNT accepts the additional keyword arguments :TEST and :TEST-NOT. These give you a compact way to write a test that involves a second value. Compare the following equivalent forms:

; Using COUNT-IF and LAMBDA 
(count-if #'(lambda (n) (< 3 n)) '(1 2 3 4 5 6 7))

; Using COUNT and :TEST 
(count 3 '(1 2 3 4 5 6 7) :test #'<)

The keyword arguments for comparison predicates also let you define the precise meaning of equality. The default predicate is EQL, which is true for identical numbers and symbols. See Chapter 17 for more information on comparison predicates.

REMOVE, SUBSTITUTE, and other sequence changers

REMOVE removes all occurrences of a specified element from a sequence.

? (remove 7 '(1 2 3 a b c t nil 7 0 7 7))
(1 2 3 A B C T NIL 0)

Keyword arguments are handled in the same way as for COUNT. REMOVE-IF and REMOVE-IF-NOT are also available; their keyword arguments are handled in the same way as for COUNT-IF and COUNT-IF-NOT.

A :COUNT keyword argument lets you limit the number of matching elements to remove.

SUBSTITUTE changes all occurrences of a specified element in a sequence to another value.

? (substitute '(q) 7 '(1 2 3 a b c t nil 7 0 7 7))
(1 2 3 A B C T NIL (Q) 0 (Q) (Q))

Keyword arguments are handled in the same way as for COUNT. SUBSTITUTE-IF and SUBSTITUTE-IF-NOT are also available; their keyword arguments are handled in the same way as for COUNT-IF and COUNT-IF-NOT.

A :COUNT keyword argument lets you limit the number of matching elements to substitute.

REMOVE-DUPLICATES returns a copy of a sequence, modified so that every element is different.

? (remove-duplicates '(1 2 3 a b c (1 2 3) f c g c h b i a j b a k a))
(1 2 3 (1 2 3) F G C H I J B K A)

The last copy of each identical element is retained in the result, unless you specify the keyword argument :FROM-END T, which causes the first copy of each identical element to be retained.

REMOVE-DUPLICATES also accepts the same keyword arguments as COUNT. The :TEST and :TEST-NOT keyword arguments let you specify the comparison predicate used to determine whether elements are identical. The default predicate is EQL, which is true for identical numbers and symbols. See Chapter 17 for more information on comparison predicates.

DELETE, REMOVE-DUPLICATES, DELETE-DUPLICATES, and NSUBSTITUTE.

Many of the functions in the preceeding section have destructive counterparts. The result of the destructive functions is identical, but the input sequence may be destructively modified.

Nondestructive    Destructive
--------------    -----------
REMOVE            DELETE
REMOVE-IF         DELETE-IF
REMOVE-IF-NOT     DELETE-IF-NOT
SUBSTITUTE        NSUBSTITUTE
SUBSTITUTE-IF     NSUBSTITUTE-IF
SUBSTITUTE-IF-NOT NSUBSTITUTE-IF-NOT
REMOVE-DUPLICATES DELETE-DUPLICATES

Remember that you must not depend upon the modification of the input sequences. The only result guaranteed to be correct is the return value of the function.

FILL and REPLACE

FILL destructively modifies a sequence, replacing every element with a new value. It accepts keyword arguments for :START and :END positions; these have the same meaning as described earlier in this chapter. The modified sequence is returned as the value of FILL.

? (fill (list 1 1 2 3 5 8) 7)
(7 7 7 7 7 7)
? (fill (list 1 1 2 3 5 8) '(a b))
((A B) (A B) (A B) (A B) (A B) (A B))
? (fill (list 1 1 2 3 5 8) 7 :start 2 :end 4)
(1 1 7 7 5 8)

REPLACE copies elements from one sequence into another, destructively modifying the target sequence. You can specify the range of elements to use in both sequences; the shorter of the two ranges determines the number of elements that is actually copied.

? (let ((a (list 1 2 3 4 5 6 7))
        (b (list 9 8 7 6 5 4 3)))
    (replace a b))

(9 8 7 6 5 4 3)
? (let ((a (list 1 2 3 4 5 6 7))
        (b (list 9 8 7 6 5 4 3)))
    (replace a b :start1 2))

(1 2 9 8 7 6 5)
? (let ((a (list 1 2 3 4 5 6 7))
        (b (list 9 8 7 6 5 4 3)))
    (replace a b :start1 2 :end1 5))
(1 2 9 8 7 6 7)
? (let ((a (list 1 2 3 4 5 6 7))
        (b (list 9 8 7 6 5 4 3)))
    (replace a b :start1 2 :end1 5 :start2 3))
(1 2 6 5 4 6 7)
? (let ((a (list 1 2 3 4 5 6 7))
        (b (list 9 8 7 6 5 4 3)))
    (replace a b :start1 2 :end1 5 :start2 3 :end2 4))
(1 2 6 4 5 6 7)

Locating things in sequences: POSITION, FIND, SEARCH, and MISMATCH

POSITION searches a sequence for a matching element, and returns the index of the first match or NIL if no matching element is in the sequence.

? (position #\a "This is all about you, isn't it?")
8
? (position #\! "This is all about you, isn't it?")
NIL

FIND is similar to POSITION except that the matching element -- rather than its index in the sequence -- is returned if there is a match. As with POSITION, you'll find the usual keyword arguments (:FROM-END, :START, :END, :KEY -- and for the "base" function, :TEST and :TEST-NOT) and function variants (i.e. FIND-IF and FIND-IF-NOT).

? (find #\a "This is all about you, isn't it?")
#\a
? (find #\! "This is all about you, isn't it?")
NIL

SEARCH returns the starting position of one sequence within another sequence, or NIL if no match is found.

? (search "ab" "This is all about you, isn't it?")
12
? (search "not so" "This is all about you, isn't it?")
NIL

SEARCH accepts :FROM-END, :KEY, :TEST and :TEST-NOT keyword arguments with the usual interpretations. You can specify a range in the substring (the first argument) using :START1 and :END1 keywords, and in the target string using the :START2 and :END2 keywords.

MISMATCH is the functional complement to SEARCH -- it returns the first position at which the substring fails to match a portion of the target string.

? (mismatch "banana" "bananananono")
6
? (mismatch "." "...hello")
1
? (mismatch "............." "...hello")
3

SORT and MERGE round out the sequence toolkit

SORT destructively sorts a sequence; the order is determined by a predicate which you supply.

? (sort (list 9 3 5 4 8 7 1 2 0 6) #'>)
(9 8 7 6 5 4 3 2 1 0)
? (sort (list 9 3 5 4 8 7 1 2 0 6) #'<)
(0 1 2 3 4 5 6 7 8 9)

The input sequence is destructively modified -- you must use the function result.

STABLE-SORT preserves the original order of identical elements; SORT may not.

You can sort structured elements (e.g. lists, structures) by using the :KEY keyword argment to specify a key extraction function.

MERGE combines two input sequences into a single result. Elements are interleaved according to the predicate. Either input sequence may be destructively modified. You must designate the type of the result.

? (merge 'vector (list 1 3 5 9 8) (vector 2 6 4 7 0) #'>)
#(2 6 4 7 1 3 5 9 8 0)
? (merge 'list (list 1 3 5 9 8) (vector 2 6 4 7 0) #'<)
(1 2 3 5 6 4 7 0 9 8)
? (merge 'vector (list 1 3 5 8 9) (vector 0 2 4 6 7) #'>)
#(1 3 5 8 9 0 2 4 6 7)
? (merge 'list (list 1 3 5 8 9) (vector 0 2 4 6 7) #'<)
(0 1 2 3 4 5 6 7 8 9)

Note that -- in the general case -- MERGE does not sort the catenation of its arguments. The predicate is used to select from one or the other of the input sequences; input from the selected sequence continues until the sense of the predicate changes. Look at the examples until you understand this.

MERGE accepts a :KEY keyword argument having the conventional meaning.