Exercise 2.61 -- 2.62

Exercise 2.61

Give an implementation of adjoin-set using the ordered representtation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.

Solution

(define (adjoin-set x set)
  (cond ((null? set) (cons x set))
        ((< (car set) x) (cons (car set) (adjoin-set x (cdr set))))
        ((= (car set) x) set)
        (else (cons x set))))

Exercise 2.62

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

Solution

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((< (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1) set2)))
        ((> (car set1) (car set2))
         (cons (car set2) (union-set set1 (cdr set2))))
        ((= (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1) (cdr set2))))))