LISP - Set

Lisp - Set Operations on Lists

Common Lisp treats lists as the default data structure for representing sets. A “set” in this context is simply a list that should not contain duplicate elements. Lisp provides a suite of functions for performing standard set operations like union, intersection, and difference on these lists.

Important Note: For applications requiring high-performance set operations on large datasets, using a hash table is a much more efficient approach. List-based operations have a performance characteristic that degrades linearly with the size of the lists (O(n*m)).

Building and Modifying Sets

The adjoin function and pushnew macro are the primary tools for adding elements to a list-based set.

Using adjoin and pushnew

adjoin is a non-destructive function. It checks if an item is already in the list. If not, it returns a new list with the item added to the front. If the item is already present, it returns the original list. It does not modify the original list.

pushnew is a convenient macro that modifies a place (like a variable) by adding an item only if it’s not already present. It effectively combines adjoin and setf.

(let ((my-set '(c b a)))
  (print "--- Using adjoin (non-destructive) ---")
  (print (adjoin 'd my-set))   ; Returns a new list with 'd
  (print (adjoin 'a my-set))   ; Returns the original list
  (print my-set)             ; Original list is unchanged

  (print "--- Using pushnew (destructive) ---")
  (pushnew 'd my-set)          ; Modifies my-set, adds 'd
  (print my-set)
  (pushnew 'a my-set)          ; Does nothing, 'a is already there
  (print my-set))

Output

"--- Using adjoin (non-destructive) ---"
(D C B A)
(C B A)
(C B A)
"--- Using pushnew (destructive) ---"
(D C B A)
(D C B A)

Testing for Membership

The member function checks if an item is an element of a list. A key Lisp idiom is that member doesn’t just return T (true). If it finds the item, it returns the sublist starting from that item. This is a “generalized boolean” because any value other than NIL is considered true.

(let ((my-set '(a b c d)))
  (print (member 'c my-set))  ; Found, returns the rest of the list
  (print (member 'x my-set))  ; Not found, returns NIL

  ;; Using it as a predicate
  (if (member 'b my-set)
      (print "'b is in the set")
      (print "'b is not in the set")))

Output

(C D)
NIL
"'b is in the set"

Comparing Complex Elements with :test and :key

By default, set functions use eql for comparison, which checks for object identity. This is fine for symbols and numbers but fails for comparing equivalent strings or structures. Use the :test keyword argument to provide a different comparison function, like #'equal (for structurally similar objects) or #'equalp (for case-insensitive string comparison).

;; Define a list of lists
(let ((list-of-lists '((1 2) (3 4))))

  ;; Fails with default test (eql)
  (print (member '(1 2) list-of-lists))
  ; => NIL

  ;; Succeeds with `equal` test
  (print (member '(1 2) list-of-lists :test #'equal))
  ; => ((1 2) (3 4))
)

Core Set Operations

Lisp provides non-destructive functions for union, intersection, and set-difference. Their destructive counterparts (nunion, nintersection, nset-difference) exist for performance optimization but should be used with caution as they may modify the input lists.

Example: union, intersection, and set-difference

(let ((set-a '(1 2 3 4))
      (set-b '(3 4 5 6)))

  ;; UNION: Elements in either set
  (print (union set-a set-b))
  ; => (1 2 3 4 5 6) or some permutation

  ;; INTERSECTION: Elements in both sets
  (print (intersection set-a set-b))
  ; => (3 4) or (4 3)

  ;; SET-DIFFERENCE: Elements in A but not in B
  (print (set-difference set-a set-b))
  ; => (1 2) or (2 1)

  ;; SET-DIFFERENCE: Elements in B but not in A
  (print (set-difference set-b set-a))
  ; => (5 6) or (6 5)
)

To ensure a list contains only unique elements, as a true set would, you can use the remove-duplicates function.

(remove-duplicates '(a b a c b d a) :test #'eql)

Output

(B C D A)