LISP - Searching a List

Lisp - Searching in Lists

Common Lisp offers a comprehensive suite of functions for searching within lists and other sequences. Understanding these tools is key to processing data effectively. The functions are highly flexible, allowing searches based on value, position, or arbitrary conditions.

Searching by Value: find and position

The most basic search operations look for a specific item in a list. find returns the item itself, while position returns its zero-based index.

Syntax

(find item sequence &key :test :key)
(position item sequence &key :test :key)

Key Arguments

• item: The element to search for.
• sequence: The list (or other sequence) to be searched.
• :test: A function used for comparison. Defaults to #'eql. Use #'equal for strings and #'equalp for case-insensitive string comparison.
• :key: A function to be applied to each element of the sequence before the comparison is made.

Return Value

Both functions return the desired result (the item or its index) on the first match. If no match is found, they return NIL.

Example: Using find and position

(let ((my-list '(10 20 30 40 50))
      (people '((:name "Alice" :age 30) (:name "Bob" :age 25))))

  ;; Simple search: find the item 30
  (format t "Find 30: ~a~%" (find 30 my-list))

  ;; Simple search: find the position of 30
  (format t "Position of 30: ~a~%" (position 30 my-list))

  ;; Search for a non-existent item
  (format t "Position of 99: ~a~%" (position 99 my-list))

  ;; Advanced search: find the person struct with name "Bob"
  ;; :key extracts the :name value before comparing with "Bob"
  ;; :test must be `equal` to compare strings
  (let ((bob (find "Bob" people :key #' (lambda (p) (getf p :name)) :test #'equal)))
    (format t "Found person: ~a~%" bob)))

Output

Find 30: 30
Position of 30: 2
Position of 99: NIL
Found person: (:NAME "Bob" :AGE 25)

Searching by Condition: find-if and position-if

Often, you don’t want to find a specific value, but rather the first element that satisfies a certain condition. This is where find-if and its relatives shine. They take a predicate function as an argument.

Syntax

(find-if predicate sequence &key :key)
(position-if predicate sequence &key :key)

Arguments

• predicate: A function that accepts one argument and returns T (true) or NIL (false). The search looks for the first element for which the predicate returns T.
• sequence: The list to be searched.

Returns

find-if returns the first matching element, while position-if returns its index. Both return NIL if no element satisfies the predicate.

Example: Finding the First Odd Number

(let ((numbers '(2 4 6 3 7 8)))

  ;; `oddp` is a built-in predicate that returns T if a number is odd.
  (format t "First odd number: ~a~%" (find-if #'oddp numbers))

  (format t "Position of first odd number: ~a~%" (position-if #'oddp numbers))

  ;; You can also use `find-if-not` to find the first element that *doesn't* satisfy the predicate.
  (format t "First number that is not even: ~a~%" (find-if-not #'evenp numbers)))

Output

First odd number: 3
Position of first odd number: 3
First number that is not even: 3

Choosing the Right Search Function

Here’s a quick guide to help you decide which function to use:

• To get an item back: Use find (for a specific value) or find-if (for a condition).
• To get an index: Use position or position-if.
• Just to check for existence: member (or member-if) is often more idiomatic. It returns the rest of the list starting from the found element, which is a true value, or NIL if not found. For example: (if (member 30 my-list) ...).

Common Pitfalls

• Forgetting :test for strings: When searching for a string in a list, the default test #'eql will usually fail because it checks for object identity, not structural equality. Always use (find "my-string" list :test #'equal).
• Confusing find and find-if: Remember that find takes an item as its first argument, while find-if takes a function (a predicate).