Next: Sorting and Merging Up: Sequences Previous: Modifying Sequences
Common Lisp the Language, 2nd Edition
Next: Sorting and Merging
Up: Sequences
Previous: Modifying
Sequences
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 :keyIf 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 (MAPPING-DESTRUCTIVE-INTERACTION) to
restrict user side effects; see section 7.9.
[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 :keyIf 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 (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[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 :keyThe 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 (MAPPING-DESTRUCTIVE-INTERACTION) to
restrict user side effects; see section 7.9.
[Function]
mismatchsequence1sequence2&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 (MAPPING-DESTRUCTIVE-INTERACTION) to
restrict user side effects; see section 7.9.
[Function]
searchsequence1sequence2&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 (MAPPING-DESTRUCTIVE-INTERACTION) to
restrict user side effects; see section 7.9.
Next: Sorting and Merging
Up: Sequences
Previous: Modifying
Sequences
AI.Repository@cs.cmu.edu