LISP - Set Difference

Lisp - Set Operations: set-difference

In Lisp, lists can be treated as sets. The set-difference function calculates the difference between two sets, returning a new list containing elements from the first list that do not appear in the second list.

Syntax

(set-difference list-1 list-2 &key :test :test-not :key)

Arguments & Keywords

• list-1: The primary list from which to take elements.
• list-2: The list of elements to remove from list-1.
• :test: A function used to compare elements. Defaults to #'eql, which works for symbols and numbers but not for strings or nested lists. Use #'equal for general-purpose comparison.
• :key: A function to apply to each element before comparison. Useful for comparing objects based on one of their attributes.

Example 1: Simple Number and Symbol Sets

For simple data like numbers or symbols, the default :test of #'eql is sufficient.

(let ((set-a '(1 2 3 4 5))
      (set-b '(3 4)))
  (let ((result (set-difference set-a set-b)))
    (format t "Result of A - B: ~a~%" result)))

(let ((set-c '(a b c d))
      (set-d '(b d e)))
  (let ((result (set-difference set-c set-d)))
    (format t "Result of C - D: ~a~%" result)))

Expected Output

Note: The order of elements in the result is not guaranteed.

Result of A - B: (1 2 5)
Result of C - D: (A C)

Example 2: Using :test for Strings and Nested Lists

When working with strings or complex data like nested lists, you must provide an appropriate :test function, such as #'string= or #'equal.

;; For strings, you must use a string comparison function
(let ((fruit-bowl-1 '("apple" "banana" "cherry"))
      (fruit-bowl-2 '("banana" "date")))
  (let ((result (set-difference fruit-bowl-1 fruit-bowl-2 :test #'string=)))
    (format t "String difference: ~a~%" result)))

;; For nested lists, use #'equal
(let ((list-of-lists-1 '((1 2) (3 4) (5 6)))
      (list-of-lists-2 '((3 4) (7 8))))
  (let ((result (set-difference list-of-lists-1 list-of-lists-2 :test #'equal)))
    (format t "List of lists difference: ~a~%" result)))

Expected Output

String difference: ("apple" "cherry")
List of lists difference: ((1 2) (5 6))

Example 3: Using :key for Complex Objects

The :key argument is powerful. It lets you perform the set difference based on a specific part of each element, like an ID or a name.

;; Define a simple structure for our example
(defstruct user id name)

(let ((all-users (list (make-user :id 1 :name "Alice")
                     (make-user :id 2 :name "Bob")
                     (make-user :id 3 :name "Charlie")))
      (banned-users (list (make-user :id 3 :name "Charlie")
                        (make-user :id 4 :name "David"))))

  ;; We want the difference based on the :id slot.
  (let ((active-users (set-difference all-users banned-users :key #'user-id)))
    (format t "Active users: ~a~%" active-users)))

Expected Output

Active users: (#S(USER :ID 1 :NAME "Alice") #S(USER :ID 2 :NAME "Bob"))

Destructive Version: nset-difference

Lisp also provides nset-difference, a destructive version of this function. It may modify the underlying list structure of list-1 to produce the result, which can be more memory-efficient.

Syntax

(nset-difference list-1 list-2 &key :test :test-not :key)

Key Considerations and Warnings

• set-difference is non-destructive: It always returns a fresh list, leaving the original lists untouched. This is generally safer.
• nset-difference is destructive: It is allowed to reuse the memory of the first list. You should not rely on the original list-1 being valid after the call. Use it only in performance-critical sections where you no longer need the original list.
• Order is Not Guaranteed: Remember that these are set operations. The order of elements in the returned list is not specified and may vary between Lisp implementations.
• Always provide :test for complex data: Forgetting to use :test #'equal for lists of lists or :test #'string= for lists of strings is a very common bug.