SICP Exercise 2.59: Unioning Unordered Sets

Implement the union-set operation for the unordered-list representation of sets.

The implementation of union-set is similar in many respects to intersection-set. We can use a recursive strategy and, if we know how to form the union of set2 and the cdr of set1 then we only need to decide whether to include the car of set1 in this, which depends upon whether (car set1) is also in set2. However, the logic gets flipped around.

To begin with, the union of any set S with the empty set is the set S (as opposed to the intersection of any set with the empty set, which is the empty set). We'll need two clauses in our cond to cope with this: if set1 is null then the union of the two sets is set2, while if set2 is null then the union of the two sets is set1.

Next, while the decision as to whether to include the car of set1 in the result depends upon whether (car set1) is also in set2, the decision is inverted. For intersections we include (car set1) in the result if it's also in set2. For unions we reverse this and only include (car set1) if it's not in set2. Why do we invert it? We need to invert this logic as our base case is when set1 is null, in which case we use set2 as the result. We're therefore adding elements of set1 onto set2 to produce the union of the two sets and so, in order to ensure there are no duplicates, we need to exclude any elements of set1 that are already in set2.

Here's the procedure:

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else (cons (car set1)
                    (union-set (cdr set1) set2)))))

...and here it is in action:

(union-set '() (list 1 2 3 4 5))
'(1 2 3 4 5)
(union-set (list 1 2 3 4 5) '())
'(1 2 3 4 5)
(union-set (list 1 2 4 6 7) (list 2 3 4 5 8))
'(1 6 7 2 3 4 5 8)