SICP Exercise 2.59

2023-01-30

Question

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

Answer

The following works:

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

Note that this really does create an unordered list, as can be seen from the following example:

(define s1 '(1 2 3))
(define s2 '(4 5 6))
(union-set s1 s2)

Result:

(3 2 1 4 5 6)