Common Lisp the Language, 2nd Edition


next up previous contents index
Next: Sorting and Merging Up: Sequences Previous: Modifying Sequences

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 
find-if predicate sequence &key :from-end :start :end :key 
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.

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


[Function]

position item sequence &key :from-end :test :test-not 
          :start :end :key 
position-if predicate sequence &key :from-end 
          :start :end :key 
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.)

change_begin
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   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


change_end


[Function]

count item sequence &key :from-end :test :test-not :start :end :key 
count-if predicate sequence &key :from-end :start :end :key 
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.

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


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

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


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

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



next up previous contents index
Next: Sorting and Merging Up: Sequences Previous: Modifying Sequences


AI.Repository@cs.cmu.edu