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