LISP - Adding elements to the Set

Lisp - Implementing Sets with Lists

While Common Lisp doesn’t include a built-in set data structure, it provides powerful tools to implement set-like behavior using lists. A key property of a set is that it contains no duplicate elements. This tutorial explores modern and idiomatic ways to create and manage sets using lists, focusing on best practices and performance considerations.

Method 1: Using adjoin

• The adjoin function is a clean, functional way to add an element to a list-based set.
• It first checks if the element is already present. If found, it returns the original list unmodified. If not, it returns a new list with the element added to the front.
• Because adjoin is non-mutating (it doesn’t change the original list), you must use setf to update the variable holding your set.
• By default, adjoin uses eql for comparison. You can provide a different test function using the :test keyword argument.

main.lisp

;; Define a variable to hold our set, represented by a list.
(defvar *my-set* '(1 2 3))

(format t "Original set: ~a~%" *my-set*)

;; Add a new element. `adjoin` returns a new list.
;; We use `setf` to update *my-set* to this new list.
(setf *my-set* (adjoin 4 *my-set*))

(format t "After adding 4: ~a~%" *my-set*)

;; Try to add a duplicate element. `adjoin` will see that 2 is already
;; a member and return the list unchanged.
(setf *my-set* (adjoin 2 *my-set*))

(format t "After attempting to add 2 again: ~a~%" *my-set*)

Output

Executing this code produces the following result:

Original set: (1 2 3)
After adding 4: (4 1 2 3)
After attempting to add 2 again: (4 1 2 3)

Method 2: Using the pushnew Macro

• pushnew is a macro that provides a more concise, imperative way to add an element to a list-based set.
• Like adjoin, it first checks for the element’s existence before adding it.
• Crucially, pushnew modifies the place (the variable) directly. You do not use setf with pushnew.
• This makes the code for adding elements shorter and is often preferred for its directness.

main.lisp

;; Define a variable to hold our set.
(defvar *my-set* '(1 2 3))

(format t "Original set: ~a~%" *my-set*)

;; Add a new value. `pushnew` modifies *my-set* in place.
(pushnew 4 *my-set*)

(format t "After adding 4: ~a~%" *my-set*)

;; Try to add a duplicate value. The list is not modified.
(pushnew 2 *my-set*)

(format t "After attempting to add 2 again: ~a~%" *my-set*)

Output

The output is identical to the adjoin example:

Original set: (1 2 3)
After adding 4: (4 1 2 3)
After attempting to add 2 again: (4 1 2 3)

Performance and Alternative Implementations

List-based sets are simple and effective for small collections. However, it’s crucial to understand their performance characteristics. Checking for membership in a list takes linear time, O(n), because the system might have to scan the entire list. For large sets or performance-critical code, this can become a bottleneck.

High-Performance Sets with Hash Tables

For superior performance, a hash table is the ideal data structure for implementing a set. Hash tables provide constant time, O(1), for average-case additions, deletions, and membership checks. Here’s a brief example of how you could manage a set using a hash table:

;; Create a hash table to represent the set. The values can be `t`.
(defvar *my-hash-set* (make-hash-table))

;; Function to add an element to our hash set
(defun add-to-hash-set (element set)
  (setf (gethash element set) t))

;; Function to check for membership
(defun in-hash-set-p (element set)
  (nth-value 0 (gethash element set)))

;; Add elements
(add-to-hash-set 'apple *my-hash-set*)
(add-to-hash-set 'banana *my-hash-set*)

(format t "Is 'apple in the set? ~a~%" (in-hash-set-p 'apple *my-hash-set*))
(format t "Is 'orange in the set? ~a~%" (in-hash-set-p 'orange *my-hash-set*))

Output

Is 'apple in the set? T
Is 'orange in the set? NIL

Key Considerations and Best Practices

• Choosing the Right Tool: Use list-based sets for convenience and small data sets. Switch to hash-table-based sets when performance with large data sets is a concern.
• Element Equality: Both adjoin and pushnew accept a :test keyword argument to specify the comparison function (e.g., #'equal for comparing strings or nested lists, #'equalp for case-insensitive string comparison). For example: (pushnew "HELLO" my-string-set :test #'equalp).
• Order is Not Guaranteed: Remember that sets are fundamentally unordered collections. While adjoin and pushnew add elements to the front of a list, you should not rely on this order. If order is important, you need a different data structure or must explicitly sort the list after modifications using (sort my-list #'<).