LISP - Search Element in Sequence

Modern Lisp: Searching Sequences

Common Lisp provides a unified and powerful set of functions for searching within sequences. A sequence is an ordered collection of elements, and the most common types are lists, vectors, and strings. These search functions are polymorphic, meaning they work seamlessly across these different data types.

Fundamental Search Functions

The three fundamental functions for searching sequences are find, position, and count.

find - Locating the First Matching Item

find searches a sequence for an item. If a match is found, it returns the item itself. If no match is found, it returns NIL.

(let ((my-vector #(10 20 30 40)))
  (format t "Find 30: ~a~%" (find 30 my-vector))   ; -> 30
  (format t "Find 99: ~a~%" (find 99 my-vector)))  ; -> NIL

position - Finding the Index of an Item

position searches a sequence for an item and returns the zero-based index of the first match. If no match is found, it returns NIL.

(let ((my-list '(a b c d)))
  (format t "Position of 'c: ~a~%" (position 'c my-list)) ; -> 2
  (format t "Position of 'x: ~a~%" (position 'x my-list)))  ; -> NIL

count - Counting Occurrences of an Item

count returns the total number of times an item appears in a sequence. If the item is not found, it returns 0.

(let ((my-string "hello world"))
  (format t "Count of #\l: ~a~%" (count #\l my-string)) ; -> 3
  (format t "Count of #\z: ~a~%" (count #\z my-string))) ; -> 0

Unlocking Power with Keyword Arguments

The true power of these functions is revealed through their keyword arguments, which allow for highly flexible and expressive searches.

1. :test - Specifying the Equality Predicate

By default, search functions use #'eql for comparison. The :test argument allows you to specify a different function, like #'equal for structural equality or #'string-equal for case-insensitive string comparison.

(let ((str-list '("apple" "Banana" "CHERRY")))
  (format t "Find 'banana' (case-sensitive): ~a~%" (find "banana" str-list :test #'equal))
  (format t "Find 'banana' (case-insensitive): ~a~%" (find "banana" str-list :test #'string-equal)))

2. :key - Searching Based on a Part of an Element

The :key argument takes a function that is applied to each element before the comparison is made. This is incredibly useful for searching in sequences of complex objects.

;; First, define a simple structure for a person
(defstruct person name age)

(let ((people (list (make-person :name "Alice" :age 30)
                    (make-person :name "Bob" :age 25)
                    (make-person :name "Charlie" :age 35))))

  ;; Find the person object whose name is "Bob"
  (let ((found-person (find "Bob" people :key #'person-name :test #'equal)))
    (format t "Found person: ~a~%" found-person))

  ;; Count how many people are older than 28
  (format t "Count of people over 28: ~a~%"
          (count-if (lambda (age) (> age 28)) people :key #'person-age)))

3. :from-end, :start, :end - Searching Subsequences

These arguments allow you to restrict the search to a specific part of the sequence. :from-end starts the search from the right, while :start and :end define a range.

(let ((data '(1 2 3 1 2 3)))
  (format t "Position of 2 (from left): ~a~%" (position 2 data))             ; -> 1
  (format t "Position of 2 (from right): ~a~%" (position 2 data :from-end t)) ; -> 4
  (format t "Position of 1 (in range 2-5): ~a~%" (position 1 data :start 2 :end 5))) ; -> 3

Searching with Predicates: find-if, position-if, count-if

For even more flexibility, Lisp provides variants that search for elements satisfying a given predicate function, rather than matching a specific item. These are named with an -if suffix (e.g., find-if).

Example: Finding the First Even Number

(let ((numbers '(1 3 5 8 9 10)))
  (format t "First even number: ~a~%" (find-if #'evenp numbers))
  (format t "Position of first even number: ~a~%" (position-if #'evenp numbers))
  (format t "Count of even numbers: ~a~%" (count-if #'evenp numbers)))

Output

First even number: 8
Position of first even number: 3
Count of even numbers: 2

Practical Advice

• Boolean Context: Remember that functions like find and position return NIL for failure and a non-NIL value for success. This means you can use their results directly in conditional expressions like if and when.
• Choosing the Right Tool: Use find/position/count when you have a specific item to find. Use the -if variants when you are looking for an item that has a certain property.