14.4 Поиск элементов последовательностей

Каждая из этих функций ищет в последовательности элемент, удовлетворяющий некоторому условию.

[Функция] 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

Если последовательность sequence содержит элемент, удовлетворяющий условию, тогда возвращается первый найденный слева элемент, иначе возвращается nil.

Если заданы параметры :start и :end, тогда поиск осуществляется в этом интервале.

Если :from-end указан в не-nil, тогда результатом функции будет найденный элемент справа.

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

Пользователь ограничен в создании побочных действий так, как это описано в разделе 7.9

[Функция] 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

Если последовательность sequence содержит элемент, удовлетворяющий условию, тогда возвращается позиция найденного элемента слева, иначе возвращается nil.

Если заданы параметры :start и :end, тогда поиск осуществляется в этом интервале. Однако возвращаемый индекс будет относиться ко всей последовательности в целом.

Если :from-end указан в не-nil, тогда результатом функции будет индекс найденного элемент справа. (Однако, возвращаемый индекс, будет, как обычно, принадлежать нумерации слева направо.)

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

Пользователь ограничен в создании побочных действий так, как это описано в разделе 7.9

Ниже приведены несколько примеров использования нескольких функций, преимущественно position-if и find-if, для обработки строк. Также используется loop.

(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!"))))))

Вот пример поведения этой функции

(setq panama     ;Предполагаемый палиндром?
      "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)     ;Восстановить
   ⇒ "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     ;Первоклассный—истинный палиндром

(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     ;Другой победитель

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

[Функция] 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

Результатом является неотрицательное целое число, указывающее на количество элементов из указанной подпоследовательности, удовлетворяющих условию.

:from-end не оказывает никакого воздействия, и оставлен только для совместимости с другими функциями.

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

Пользователь ограничен в создании побочных действий так, как это описано в разделе 7.9

[Функция] mismatch sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2

Функция поэлементно сравнивает указанные подпоследовательности. Если их длины равны и соответственно равны между собой каждые их элементы, то функция возвращает nil. Иначе, функция возвращает неотрицательное целое число. Это число указывает на первый элемент слева, который не совпал с элементом другой последовательности sequence2. Или же, в случае если одна подпоследовательность короче другой, но все элементы были одинаковыми, индекс указывает на последний проверенный элемент.

Если параметр :from-end равен не-nil значению, тогда возвращается увеличенная на 1 позиция первого не совпавшего элемента справа. Фактически, (под)последовательности выравниваются по своим правым концам, затем сравниваются последние элементы, затем предпоследние и так далее. Возвращаемый индекс принадлежит первой последовательности sequence1.

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

Пользователь ограничен в создании побочных действий так, как это описано в разделе 7.9

[Функция] search sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2 :end1 :end2

Функция осуществляет поэлементный поиск последовательности sequence1 в последовательности sequence1. Если поиск не увенчался успехом, результатом является значение nil. Иначе, результат является индексом первого совпавшего элемента слева во второй последовательности sequence2.

Если аргумент :from-end равен не-nil, поиск осуществляется справа, и результат является индексом элемента слева в первой совпавшей подпоследовательности справа.

Реализация может выбирать алгоритм поиска на своё усмотрение. Количество проводимых сравнений не может быть указано точно. Например, search при :from-end равном не-nil может фактически производить поиск слева направо, но результатом будет всегда индекс самой правой совпавшей последовательности. Поэтому пользователю желательно использовать предикаты без побочных эффектов.

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

Пользователь ограничен в создании побочных действий так, как это описано в разделе 7.9