sicp-ex-2.60


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


bravely

@sgm, actually there is to improve `intersection-set`: getting all the dupes using union then filtering via strict intersection. strict version by itself only keeps dupes from the first set, not the second. didn't try to optimize though. `element-of-set` sure, stays as it is.

 (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 (intersection-set-strict set1 set2) 
   (cond ((or (null? set1) (null? set2)) '()) 
         ((element-of-set? (car set1) set2)         
          (cons (car set1) 
                (intersection-set-strict (cdr set1) set2))) 
         (else (intersection-set-strict (cdr set1) set2)))) 
  
 (define (intersection-set set1 set2) 
   (let ((inter (intersection-set-strict set1 set2)) 
         (union (union-set set1 set2))) 
     (filter (lambda (x) (element-of-set? x inter)) 
             union))) 
  
 (define (union-set set1 set2) 
   (append set1 set2)) 
  
  
 ; from racket's rackunit 
 (check-equal? (intersection-set '(0 1 1 2 2 3) '(2 2 3 4)) 
               '(2 2 3 2 2 3))