LISP - Getting SubSet from a Set

Lisp - Creating Subsets from Lists

In Common Lisp, set-like operations are typically performed on standard lists. While Lisp doesn’t have a built-in, high-performance set data type, it provides a rich suite of functions for treating lists as sets. This chapter explores modern and idiomatic ways to create subsets from these lists.

Filtering with Predicates

The most common way to create a subset is by filtering a list based on a condition. This is achieved using higher-order functions that accept a predicate—a function that returns a generalized boolean (anything other than NIL is true).

Example: Filtering for Odd Numbers

We can use remove-if-not to keep only the elements for which the predicate is true. The #' syntax is shorthand for (function ...) and is used to get the function object associated with a symbol.

;; Define a pure function to extract odd numbers from a list.
;; It does not modify the original list.
(defun get-odd-numbers (numbers)
  (remove-if-not #'oddp numbers))

;; Define a list of numbers for our example.
(let ((my-numbers '(1 2 3 4 5 6 7 8)))
  ;; Call the function and print the resulting subset.
  (print (get-odd-numbers my-numbers))

  ;; The original list remains unchanged.
  (print my-numbers))

Output

Executing this code produces the following result:

(1 3 5 7)
(1 2 3 4 5 6 7 8)

Example: Using an Anonymous (Lambda) Function

For one-off or simple predicates, defining a full function with defun is unnecessary. A lambda function is perfect for this. Here, we create a subset of numbers less than 5.

;; Use a let block to keep the scope local.
(let ((my-numbers '(1 2 3 4 5 6 7 8)))
  ;; Filter the list using an inline lambda function.
  (let ((numbers-less-than-5
          (remove-if-not #'(lambda (x) (< x 5)) my-numbers)))
    (print numbers-less-than-5)))

Output

This will output:

(1 2 3 4)

Deriving Subsets with Set Operations

Common Lisp provides standard set-theoretic functions like intersection and set-difference. These functions are non-destructive, meaning they return a new list without modifying the original inputs.

Example: Using intersection

intersection returns a list containing elements that appear in both input lists.

(let ((list-a '(1 2 3 4))
      (list-b '(3 4 5 6)))
  (let ((common-elements (intersection list-a list-b)))
    (print common-elements)))

Output

The resulting list of common elements is:

(3 4)

Example: Using set-difference

set-difference returns a list of elements that are in the first list but not in the second.

(let ((list-a '(1 2 3 4))
      (unwanted-elements '(2 4)))
  (let ((remaining-elements (set-difference list-a unwanted-elements)))
    (print remaining-elements)))

Output

The result is list-a with the unwanted elements removed:

(1 3)

Extracting Subsequences with subseq

The subseq function extracts a contiguous portion of any sequence (like a list, vector, or string). It is not a set operation but is a common way to get a “subset” based on position.

Example: Getting a slice of a list

subseq takes a sequence, a zero-indexed start position, and an optional, non-inclusive end position.

;;           indices: 0  1  2  3  4  5
(let ((my-sequence '(a b c d e f)))
  ;; Get elements from index 1 up to (but not including) index 4
  (let ((slice (subseq my-sequence 1 4)))
    (print slice)))

Output

The resulting subsequence is:

(B C D)

Best Practice: For clarity and predictability, prefer non-destructive functions like remove-if-not, intersection, and set-difference. Their destructive counterparts (delete-if-not, nintersection, nset-difference) can offer performance benefits in specific, controlled situations but risk introducing subtle bugs by modifying shared data.