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.59

From Drewiki
Jump to: navigation, search

Problem

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

Solution

This is a straightforward problem. We only need to cdr down one set and remember to check both sets for the empty set condition, in which case all of the remaining elements of the other set are added to the union set result.

(define true #t)
 
(define false #f)
 
(define (element-of-set? x set) 
  (cond ((null? set) false) 
        ((equal? x (car set)) true) 
        (else (element-of-set? x (cdr set))))) 
 
(define (adjoin-set x set) 
  (if (element-of-set? x set) 
      set 
      (cons x set))) 
 
(define (intersection-set set1 set2) 
  (cond ((or (null? set1) (null? set2)) '()) 
        ((element-of-set? (car set1) set2)        
         (cons (car set1) 
               (intersection-set (cdr set1) set2))) 
        (else (intersection-set (cdr set1) set2)))) 
 
(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)))))

Tests:

(define s1 '(a b c))
(define s2 '(b d e))
(define s3 '(z))
(define s4 '())
 
(union-set s1 s1)

Output:

(a b c)
(union-set s1 s2)

Output:

(a c b d e)
(union-set s2 s1)

Output:

(d e a b c)
(union-set s1 s3)

Output:

(a b c z)
(union-set s3 s1)

Output:

(z a b c)
(union-set s3 s4)

Output:

(z)
(union-set s4 s3)

Output:

(z)
(union-set s4 s4)

Output:

()
Personal tools