LISP - Set Intersection

Lisp - Set Intersection

In set theory, an intersection of two sets is the set of elements that are common to both. Common Lisp provides powerful, built-in functions to perform this operation on lists, which are often used to represent sets.

Non-Destructive Intersection: intersection

The intersection function returns a new list containing elements present in both input lists. It is non-destructive, meaning the original lists are not modified.

Syntax

(intersection list1 list2 &key test test-not key) -> result-list

Key Arguments

• list1, list2: The two lists to compare.
• :test: A function of two arguments used to compare elements. Defaults to #'eql.
• :test-not: The inverse of :test. An element is a match if this function returns NIL.
• :key: A function of one argument applied to each element before comparison. This is extremely useful for complex data.

Examples

Example 1: Intersection of Numbers

(let ((set-a '(1 2 3 4 5))
      (set-b '(4 5 6 7 8)))
  (format t "Set A: ~a~%" set-a)
  (format t "Set B: ~a~%" set-b)
  (format t "Intersection: ~a~%" (intersection set-a set-b)))

Output

Set A: (1 2 3 4 5)
Set B: (4 5 6 7 8)
Intersection: (5 4)
; Note: The order of elements in the result is not guaranteed.

Example 2: Intersection of Strings using :test

(let ((fav-fruits '("apple" "banana" "cherry"))
      (in-stock '("banana" "date" "fig")))
  (intersection fav-fruits in-stock :test #'string=))

Output

("banana")

Example 3: Intersection of Complex Data using :key

Imagine you have two lists of products, represented as property lists (plists), and you want to find products that exist in both lists based on their :id.

(let ((products-A '((:id 1 :name "Laptop") (:id 2 :name "Mouse")))
      (products-B '((:id 2 :name "Gaming Mouse") (:id 3 :name "Keyboard"))))
  (intersection products-A products-B :key (lambda (p) (getf p :id))))

Output

((:ID 2 :NAME "Mouse"))

Destructive Intersection: nintersection

Lisp also provides nintersection, a destructive version. It modifies list1 to produce the result. This can be more memory-efficient as it avoids creating a new list, but it should be used with caution as it alters the original data.

When to use nintersection

Use nintersection in performance-critical code paths where you know that the original list1 is a temporary value that will not be used again.

(let ((set-a '(1 2 3 4 5))
      (set-b '(4 5 6 7)))
  (format t "Original Set A before: ~a~%" set-a)
  (let ((result (nintersection set-a set-b)))
    (format t "Result: ~a~%" result)
    (format t "Original Set A after: ~a~%" set-a)))

Output

Original Set A before: (1 2 3 4 5)
Result: (4 5)
Original Set A after: (4 5) ; The list bound to set-a has been modified!

Best Practices

• Favor intersection: For clarity and safety, prefer the non-destructive intersection unless you have a specific performance reason to use nintersection.
• Choose the Right Test: For non-numeric or complex data, always specify the appropriate :test (e.g., #'equal for strings, #'equalp for case-insensitive comparison).
• Leverage :key: For lists of structures or complex objects, :key is the idiomatic and efficient way to specify which part of the object to compare.