SICP Exercise 2.62: Unioning Sets with Ordered Representations

Give a Θ(n) implementation of union-set for sets represented as ordered lists.

Just like in exercise 2.59, the implementation of union-set is similar in many respects to intersection-set. We'll iterate through the two list representations in parallel, comparing the head items of each list at each iteration. However, unlike intersection-set, which only keeps an item if it is present in the heads of both lists, we want to keep all of the items from both lists - but we need to remove duplicates and ensure the resulting set is ordered.

So what are the cases we're going to deal with? Well:

• If set1 is null then the union is just set2.
• Conversely, if set2 is null then the union is just set1.
• If the head items of both lists are the same then we can produce the union by consing that item onto the result of generating the union of the cdrs of both lists. As with intersection-set it doesn't really matter whether we use the head if set1 or set2 for the cons, so we'll arbitrarily use the head of set1.
• If the head item of set1 precedes the head item of set2 then we can produce the union by consing the head item of set1 onto the result of generating the union of the cdr of set1 and set2.
• Conversely, if the head item of set2 precedes the head item of set1 then we can produce the union by consing the head item of set2 onto the result of generating the union of set1 and the cdr of set2.

Here's the procedure:

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (let ((x1 (car set1))
                    (x2 (car set2)))
                (cond ((= x1 x2)
                       (cons x1
                             (union-set (cdr set1)
                                        (cdr set2))))
                      ((< x1 x2)
                       (cons x1
                             (union-set (cdr set1)
                                        set2)))
                      ((< x2 x1)
                       (cons x2
                             (union-set set1
                                        (cdr set2)))))))))

Let's see it in action:

> (union-set '() '())
'()
> (union-set '(1 2 3) '())
'(1 2 3)
> (union-set '() '(4 5 6))
'(4 5 6)
> (union-set '(1 2 3) '(4 5 6))
'(1 2 3 4 5 6)
> (union-set '(4 5 6) '(1 2 3))
'(1 2 3 4 5 6)
> (union-set '(1 3 5) '(2 4 6))
'(1 2 3 4 5 6)
> (union-set '(2 4 6) '(1 3 5))
'(1 2 3 4 5 6)
> (union-set '(1 2 3) '(2 3 4))
'(1 2 3 4)