LISP - Set Union

Lisp - Set Operations: Union

In mathematics, a set is a collection of distinct elements. In Common Lisp, sets are commonly represented as lists where each element is unique. The union of two sets is a new set containing all elements that are in either of the original sets, with duplicates removed.

Common Lisp provides the built-in function union to perform this operation efficiently.

Syntax: union

(union list1 list2 &key :test :test-not :key)

Parameters

• list1, list2: The two lists (representing sets) to be combined.
• :test: A function of two arguments used to compare elements. The default is eql, which is suitable for symbols and numbers but not for comparing strings or structured lists.
• :test-not: The inverse of :test. A function that returns true if two elements are not equal.
• :key: A function of one argument that is applied to each element before comparison. Useful for comparing objects based on a specific attribute.

Example: Union of Number Sets

The simplest case is finding the union of two sets of numbers. The default :test function, eql, works perfectly here.

main.lisp

;;; Use LET to define local lexical variables, not DEFVAR.
(let ((set1 '(1 2 3 4 5))
      (set2 '(3 4 5 6 7)))
  (format t "Set 1: ~a~%" set1)
  (format t "Set 2: ~a~%" set2)

  (let ((result-set (union set1 set2)))
    (format t "Union: ~a~%" result-set)))

Output

The resulting set contains all numbers from 1 to 7, with the common elements (3, 4, 5) appearing only once. The order of elements is not guaranteed.

Set 1: (1 2 3 4 5)
Set 2: (3 4 5 6 7)
Union: (1 2 6 7 3 4 5)

Example: Union of String Sets

When working with strings, eql is not sufficient because it checks for object identity, not character-by-character equality. We must provide #'string= as the :test function.

main.lisp

(let ((set1 '("apple" "banana" "cherry"))
      (set2 '("banana" "date" "apple")))
  (format t "Set 1: ~s~%" set1)
  (format t "Set 2: ~s~%" set2)

  ;; We must specify a test for string equality.
  (let ((result-set (union set1 set2 :test #'string=)))
    (format t "Union: ~s~%" result-set)))

Output

Set 1: ("apple" "banana" "cherry")
Set 2: ("banana" "date" "apple")
Union: ("cherry" "apple" "banana" "date")

Example: Union of Complex Lists

Similarly, for sets whose elements are lists themselves, we need a test function like equal that can compare structures.

main.lisp

(let ((set1 '((1 2) (3 4)))
      (set2 '((3 4) (5 6))))
  (format t "Set 1: ~a~%" set1)
  (format t "Set 2: ~a~%" set2)

  ;; Use #'equal to compare the nested lists.
  (let ((result-set (union set1 set2 :test #'equal)))
    (format t "Union: ~a~%" result-set)))

Output

Set 1: ((1 2) (3 4))
Set 2: ((3 4) (5 6))
Union: ((1 2) (5 6) (3 4))

Destructive Union with nunion

Common Lisp also provides a destructive version of union called nunion. This function is permitted to modify the list structure of list1 to create the result. This can be more memory-efficient as it avoids allocating new cons cells, but it should be used with caution as it modifies the original data.

Syntax: nunion

(nunion list1 list2 &key :test :test-not :key)

Best Practice: Only use nunion when you are certain that the original list1 is no longer needed in its original form.

main.lisp

(let ((set1 (list 1 2 3 4 5)) ; Use LIST to create a fresh list we can modify
      (set2 '(3 4 5 6 7)))
  (format t "Original Set 1: ~a~%" set1)

  ;; The result of nunion should be assigned back, as the head of the list might change.
  (let ((result-set (nunion set1 set2)))
    (format t "Destructive Union Result: ~a~%" result-set)
    (format t "Set 1 after NUNION: ~a (may be modified)~%" set1)))

Output

Original Set 1: (1 2 3 4 5)
Destructive Union Result: (1 2 6 7 3 4 5)
Set 1 after NUNION: (1 2 6 7 3 4 5) (may be modified)

Key Considerations

• Non-destructive vs. Destructive: union is safe and returns a new list. nunion is potentially faster but modifies its first argument.
• Choosing a :test function: This is the most common point of error. Remember to use #'string= for strings, #'equal for general lists, and #'equalp for case-insensitive string or numeric type-insensitive comparisons.
• Performance: For very large sets, representing them as simple lists can be slow (O(n*m) complexity). For high-performance applications, consider using hash tables as sets for near-constant time lookups.