Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.62

From Drewiki
Jump to: navigation, search

Problem

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

Solution

The overall structure of a θ(n) implementation of union-set is similar to that given in the text for intersection-set. The chief difference is that union-set always conses the lesser element from set1 or set2 onto the result of the recursion. The decision of which set to cdr is identical to that of intersection-set (i.e., it's the one whose element is consed onto the result).

(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)))
                      (else
                       (cons x2 (union-set set1 (cdr set2)))))))))

Tests:

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

Output:

(1 2 3 4 6 7)
(union-set s2 s1)

Output:

(1 2 3 4 6 7)
(union-set s1 '())

Output:

(1 3 6)
(union-set '() s1)

Output:

(1 3 6)
Personal tools