sicp-ex-2.60

[Top Page][Recent Changes][All Pages][Settings][Categories][Wiki Howto]
[Edit][Edit History]

 (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) 
   (cons x set)) 
  
 (define (union-set set1 set2) 
   (append set1 set2)) 
  
 (define (remove-set-element x set) 
   (define (remove-set-element-iter acc rest) 
     (cond ((null? rest) acc) 
           ((equal? x (car rest)) (append acc (cdr rest))) 
           (else (remove-set-element-iter (adjoin-set (car rest) acc) (cdr rest))))) 
   (remove-set-element-iter '() 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) (remove-set-element (car set1) set2)))) 
         (else (intersection-set (cdr set1) set2))))

<< Previous exercise (2.59) | Index | Next exercise (2.61) >>

sgm

With the need to check for pre-existence lifted, the procedure adjoin-set can be a straight cons and the time complexity drops to Θ(1).

 (define (adjoin-set x set) 
   (cons x set))

Also, union-set can now become a straight append and its time complexity drops to Θ(n).

 (define (union-set set1 set2) 
   (append set1 set2))

There isn’t any way to improve element-of-set? or intersection-set.