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

Zelphir

@bravely I got another version for keeping the duplicates, although it might not be as elegant.

 (define (element-of-duplicate-set? x set) 
   (cond [(empty? set) false] 
         [(equal? x (car set)) true] 
         [else (element-of-duplicate-set? x (cdr set))])) 
  
 (define (adjoin-duplicate-set x set) 
   (cons x set)) 
  
 (define (intersection-duplicate-set set1 set2) 
   (define (iter result s1 s2 already-swapped) 
     (cond 
       [(and (empty? s1) (empty? s2)) 
         result] 
        
       [(and (empty? s1) (not already-swapped)) 
         (iter result s2 result true)] 
  
       [(and (empty? s1) already-swapped) 
         result] 
  
       [(element-of-duplicate-set? (car s1) s2) 
         (iter (append result (list (car s1))) 
               (cdr s1) 
               s2 
               already-swapped)] 
  
       [else 
         (iter result (cdr s1) s2 already-swapped)])) 
  
   (iter '() set1 set2 false)) 
  
 (define (union-duplicate-set set1 set2) 
   (append set1 set2)) 

@bravely, if your improvement on intersection uses strict intersection, it has the same Θ(n^2) complexity, so it is not an improvement at all. Even tho the definition might look cleaner, it is in fact actually worse than traversing the first set checking whether each element is also in the other set, because your improvement will need to append the sets in the union, so it will take n steps more.

Also, we haven't answered the last question in the exercise. You should used this non-strict repeated-allowing representation (which is just any data structure, really) every time you can. The set data structure is defined by this non-repeatedness and it should be used only where this property is necessary, because the set basic operations are expensive compared to other data structures.