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:

; test set
(define set1 '(1 2 3 4 5 6 7 8 9))
(define set2 '(3 4 5 11 12 13 14))
(define set3 '(4 5 6 7))
(define set4 '(1 2 3 4 5 6 7 8 9))

; union
(print (union set1 set2))
; ==> (1 2 6 7 8 9 3 4 5 11 12 13 14)

; intersection
(print (intersect set1 set2))
; ==> (3 4 5)

; difference
(print (diff set1 set2))
; ==> (1 2 6 7 8 9)

; subset (no predefined function)
(define (subset? a b)
   (all (lambda (i) (has? b i)) a))
(print (subset? set3 set1))
; ==> #true
(print (subset? set3 set2))
; ==> #false

; equality
(print (equal? set1 set2))
; ==> #false
(print (equal? set1 set4))
; ==> #true