LISP - Set Exclusive OR

Lisp - Set Symmetric Difference (XOR)

In set theory, the symmetric difference (also known as XOR) of two sets is the set of elements which are in either of the sets, but not in their intersection. Think of it as finding the elements that are unique to each set.

Common Lisp provides the set-exclusive-or function to compute this, treating lists as representations of sets.

Modern Development Setup

To follow these examples, you’ll need a Common Lisp environment. We recommend:

• A Lisp Implementation: SBCL (Steel Bank Common Lisp) is a popular, high-performance choice.
• Quicklisp: The de-facto package manager for Common Lisp, used to install libraries.
• An Editor: Emacs with SLIME/Sly or VS Code with Alive provide an interactive development experience (REPL).

Syntax: set-exclusive-or

(set-exclusive-or list1 list2 &key test test-not key)

Parameters

• list1, list2: The two lists to be treated as sets.
• :test: A function designator (e.g., #'eql, #'equal) used to compare elements. The default is #'eql, which works for numbers and symbols but not for comparing the contents of strings or lists.
• :test-not: The inverse of :test. You would use one or the other.
• :key: A function to be applied to each element before comparison. Useful for comparing objects based on a specific attribute.

Practical Examples

The following examples use let to create local variables, which is modern best practice over using defvar for temporary example data.

Example 1: Sets of Numbers

;; main.lisp
(let ((set-a '(1 2 3 4 5))
      (set-b '(3 4 5 6 7)))
  (format t "Set A: ~a~%" set-a)
  (format t "Set B: ~a~%" set-b)

  ;; The default :test, #'eql, works fine for numbers.
  (let ((result (set-exclusive-or set-a set-b)))
    (format t "Symmetric Difference: ~a~%" result)))

Output

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

Example 2: Sets of Strings

When comparing strings, we must provide a string-comparison function like #'string=.

;; main.lisp
(let ((fruit-set-a '("apple" "banana" "cherry"))
      (fruit-set-b '("banana" "date" "fig")))
  (format t "Fruit Set A: ~a~%" fruit-set-a)
  (format t "Fruit Set B: ~a~%" fruit-set-b)

  ;; Use #'string= to compare string contents.
  (let ((result (set-exclusive-or fruit-set-a fruit-set-b :test #'string=)))
    (format t "Symmetric Difference: ~a~%" result)))

Output

Fruit Set A: ("apple" "banana" "cherry")
Fruit Set B: ("banana" "date" "fig")
Symmetric Difference: ("fig" "date" "cherry" "apple")

Example 3: Sets of Lists (Complex Structures)

To compare nested lists by their structure and content, we must use #'equal.

;; main.lisp
(let ((list-set-a '((1 2) (3 4)))
      (list-set-b '((3 4) (5 6))))
  (format t "List Set A: ~a~%" list-set-a)
  (format t "List Set B: ~a~%" list-set-b)

  ;; Use #'equal to compare nested list structures.
  (let ((result (set-exclusive-or list-set-a list-set-b :test #'equal)))
    (format t "Symmetric Difference: ~a~%" result)))

Output

List Set A: ((1 2) (3 4))
List Set B: ((3 4) (5 6))
Symmetric Difference: ((5 6) (1 2))

Destructive Operations: nset-exclusive-or

Common Lisp also provides a destructive counterpart, nset-exclusive-or. The ‘n’ prefix is a convention for functions that may modify their arguments.

Syntax: nset-exclusive-or

(nset-exclusive-or list1 list2 &key test test-not key)

Key Differences and Best Practices

• Performance: nset-exclusive-or can be more memory-efficient because it reuses the list structure of its arguments (cons cells) instead of allocating new memory. This can be faster for very large lists.
• Side Effects: This is dangerous! Because it modifies the input lists, you should only use it when you are certain the original lists are no longer needed. Using it on shared data can lead to confusing bugs.
• Rule of Thumb: Always default to the non-destructive set-exclusive-or. Only use nset-exclusive-or as a deliberate optimization in performance-critical code where you can guarantee the input lists are disposable.

Example: Destructive XOR

;; main.lisp
(let ((set-a '(1 2 3 4 5))
      (set-b '(3 4 5 6 7)))
  (format t "Original Set A before nset-exclusive-or: ~a~%" set-a)

  ;; The contents of set-a may be destroyed to create the result.
  (let ((result (nset-exclusive-or set-a set-b)))
    (format t "Symmetric Difference: ~a~%" result)
    (format t "Set A after nset-exclusive-or: ~a~%" set-a)))
    ; The value of set-a is now undefined and should not be used.

Output

Original Set A before nset-exclusive-or: (1 2 3 4 5)
Symmetric Difference: (7 6 2 1)
Set A after nset-exclusive-or: (1 2 3 4 5) ; The contents are unreliable and implementation-dependent!

Common Pitfalls & Debugging

• Wrong Test Function: Getting an empty or incorrect result often means you forgot to specify an appropriate :test function (like #'string= for strings or #'equal for nested lists).
• Unpredictable Order: Remember that lists are being treated as sets. The order of elements in the returned list is not guaranteed by the standard. Do not rely on it.
• Accidental Destruction: Using nset-exclusive-or and then trying to use the original list elsewhere is a common source of bugs. If a bug appears after an “optimization” to use a destructive function, that’s the first place to check.