Problem Statement

A   set  is a collection of elements, without duplicates and without order.

Show each of these set operations:

As an option, show some other set operations. (If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.) As another option, show how to modify a mutable set.

One might implement a set using an associative array (with set elements as array keys and some dummy value as the values). One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bit-wise binary operators). The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.

Let's start with the solution:

(setf a '(1 2 3 4))
(setf b '(2 3 4 5))

(format t "sets: ~a ~a~%" a b)

;;; element
(loop for x from 1 to 6 do
	(format t (if (member x a)
		    "~d ∈ A~%"
		    "~d ∉ A~%") x))

(format t "A ∪ B: ~a~%" (union a b))
(format t "A ∩ B: ~a~%" (intersection a b))
(format t "A \\ B: ~a~%" (set-difference a b))
(format t (if (subsetp a b)
	    "~a ⊆ ~a~%"
	    "~a ⊈ ~a~%") a b)

(format t (if (and (subsetp a b)
		   (subsetp b a))
	    "~a = ~a~%"
	    "~a ≠ ~a~%") a b)