14.4 Searching Sequences for Items

Each of these functions searches a sequence to locate one or more elements satisfying some test.

[Function] find item sequence &key :from-end :test :test-not :start :end :key
[Function] find-if predicate sequence &key :from-end :start :end :key
[Function] find-if-not predicate sequence &key :from-end :start :end :key

If the sequence contains an element satisfying the test, then the leftmost such element is returned; otherwise nil is returned.

If :start and :end keyword arguments are given, only the specified subsequence of sequence is searched.

If a non-nil :from-end keyword argument is specified, then the result is the rightmost element satisfying the test.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

[Function] position item sequence &key :from-end :test :test-not :start :end :key
[Function] position-if predicate sequence &key :from-end :start :end :key
[Function] position-if-not predicate sequence &key :from-end :start :end :key

If the sequence contains an element satisfying the test, then the index within the sequence of the leftmost such element is returned as a non-negative integer; otherwise nil is returned.

If :start and :end keyword arguments are given, only the specified subsequence of sequence is searched. However, the index returned is relative to the entire sequence, not to the subsequence.

If a non-nil :from-end keyword argument is specified, then the result is the index of the rightmost element satisfying the test. (The index returned, however, is an index from the left-hand end, as usual.)

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

Here is a simple piece of code that uses several of the sequence functions, notably position-if and find-if, to process strings. Note one use of loop as well.

(defun debug-palindrome (s)
  (flet ((match (x) (char-equal (first x) (third x))))
    (let* ((pairs (loop for c across s
                        for j from 0
                        when (alpha-char-p c)
                          collect (list c j)))
           (quads (mapcar #’append pairs (reverse pairs)))
           (diffpos (position-if (complement #’match) quads)))
      (when diffpos
        (let* ((diff (elt quads diffpos))
               (same (find-if #’match quads
                              :start (+ diffpos 1))))
          (if same
              (format nil
                      "/~A/ (at ~D) is not the reverse of /~A/"
                      (subseq s (second diff) (second same))
                      (second diff)
                      (subseq s (+ (fourth same) 1)
                                (+ (fourth diff) 1)))
              "This palindrome is completely messed up!"))))))

Here is an example of its behavior.

(setq panama     ;A putative palindrome?
      "A man, a plan, a canoe, pasta, heros, rajahs,
       a coloratura, maps, waste, percale, macaroni, a gag,
       a banana bag, a tan, a tag, a banana bag again
       (or a camel), a crepe, pins, Spam, a rut, a Rolo,
       cash, a jar, sore hats, a peon, a canal–Panama!")

(debug-palindrome panama)
   ⇒ "/wast/ (at 73) is not the reverse of /, pins/"

(replace panama "snipe" :start1 73)     ;Repair it
   ⇒ "A man, a plan, a canoe, pasta, heros, rajahs,
       a coloratura, maps, snipe, percale, macaroni, a gag,
       a banana bag, a tan, a tag, a banana bag again
       (or a camel), a crepe, pins, Spam, a rut, a Rolo,
       cash, a jar, sore hats, a peon, a canal–Panama!"

(debug-palindrome panama) ⇒ nil     ;Copacetic—a true palindrome

(debug-palindrome "Rubber baby buggy bumpers")
   ⇒ "/Rubber / (at 0) is not the reverse of /umpers/"

(debug-palindrome "Common Lisp: The Language")
   ⇒ "/Commo/ (at 0) is not the reverse of /guage/"

(debug-palindrome "Complete mismatches are hard to find")
   ⇒ 
  "/Complete mism/ (at 0) is not the reverse of /re hard to find/"

(debug-palindrome "Waltz, nymph, for quick jigs vex Bud")
   ⇒ "This palindrome is completely messed up!"

(debug-palindrome "Doc, note: I dissent.  A fast never
                   prevents a fatness.  I diet on cod.")
   ⇒nil     ;Another winner

(debug-palindrome "Top step’s pup’s pet spot") ⇒ nil

[Function] count item sequence &key :from-end :test :test-not :start :end :key
[Function] count-if predicate sequence &key :from-end :start :end :key
[Function] count-if-not predicate sequence &key :from-end :start :end :key

The result is always a non-negative integer, the number of elements in the specified subsequence of sequence satisfying the test.

The :from-end argument does not affect the result returned; it is accepted purely for compatibility with other sequence functions.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

[Function] mismatch sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2

The specified subsequences of sequence1 and sequence2 are compared element-wise. If they are of equal length and match in every element, the result is nil. Otherwise, the result is a non-negative integer. This result is the index within sequence1 of the leftmost position at which the two subsequences fail to match; or, if one subsequence is shorter than and a matching prefix of the other, the result is the index relative to sequence1 beyond the last position tested.

If a non-nil :from-end keyword argument is given, then one plus the index of the rightmost position in which the sequences differ is returned. In effect, the (sub)sequences are aligned at their right-hand ends; then, the last elements are compared, the penultimate elements, and so on. The index returned is again an index relative to sequence1.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

[Function] search sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2

A search is conducted for a subsequence of sequence2 that element-wise matches sequence1. If there is no such subsequence, the result is nil; if there is, the result is the index into sequence2 of the leftmost element of the leftmost such matching subsequence.

If a non-nil :from-end keyword argument is given, the index of the leftmost element of the rightmost matching subsequence is returned.

The implementation may choose to search the sequence in any order; there is no guarantee on the number of times the test is made. For example, search with a non-nil :from-end argument might actually search a list from left to right instead of from right to left (but in either case would return the rightmost matching subsequence, of course). Therefore it is a good idea for a user-supplied predicate to be free of side effects.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.