Rules of Sets - psholtz/MIT-SICP GitHub Wiki

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

Solution

Exercise 2.59 only asks us to implement the "union-set" operation, but it is useful to consider whether our implementation satisfies the "rules of sets" criteria specified in Footnote 37.

Let's give the definitions of the set-operation procedures:

(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))))

and we found that our most efficient implementation of "union-set" was given in terms of the "accumulate" procedure:

(define (accumulate op init seq)
  (if (null? seq)
      init
      (op (car seq)
	  (accumulate op init (cdr seq)))))

(define (union-set s1 s2)
 (accumulate (lambda (a b) (adjoin-set a b)) s2 s1))

First Rule

The first rule is to verify that (element-of-set? x (adjoin-set x S)) returns true for any set S and any object x:

(element-of-set? 1 (adjoin-set 1 '()))
;; ==> #t
(element-of-set? 1 (adjoin-set 1 '(2 3)))
;; ==> #t
(element-of-set? 1 (adjoin-set 1 '(1 2 3)))
;; ==> #t

(element-of-set? 'a (adjoin-set 'a '()))
;; ==> #t
(element-of-set? 'a (adjoin-set 'a '(2 b)))
;; ==> #t
(element-of-set? 'a (adjoin-set 'a '(a 2 b)))
;; ==> #t

Second Rule

The second rule is to verify that (element-of-set? x (union-set S T)) is equal to (or (element-of-set? x S) (element-of-set? x T)) for any sets S and T, and any object x:

(element-of-set? 1 (union-set '() '()))
;; ==> #f
(or (element-of-set? 1 '()) (element-of-set? 1 '()))
;; ==> #f

(element-of-set? 1 (union-set '(2 3) '(4 5)))
;; ==> #f
(or (element-of-set? 1 '(2 3)) (element-of-set? 1 '(4 5)))
;; ==> #f

(element-of-set? 1 (union-set '(2 3 4) '(3 4 5)))
;; ==> #f
(or (element-of-set? 1 '(2 3 4)) (element-of-set? 1 '(3 4 5)))
;; ==> #f

(element-of-set? 1 (union-set '(1 2) '(3 4)))
;; ==> #t
(or (element-of-set? 1 '(1 2)) (element-of-set? 1 '(3 4)))
;; ==> #t

(element-of-set? 1 (union-set '(1 2 3) '(2 3 4)))
;; ==> #t
(or (element-of-set? 1 '(1 2 3)) (element-of-set? 1 '(2 3 4)))
;; ==> #t

(element-of-set? 1 (union-set '(1 2 3) '(1 3 5)))
;; ==> #t
(or (element-of-set? 1 '(1 2 3)) (element-of-set? 1 '(1 3 5)))
;; ==> #t

Third Rule

The third rule is to very that (element-of-set? x '()) evaluates to false for any object x:

(element-of-set? 1 '())
;; ==> #f
(element-of-set? 'a '())
;; ==> #f