sicp-ex-2.59


<< Previous exercise (2.58) | Index | Next exercise (2.60) >>


Here's a tail-recursive implementation.

 (define (union-set s1 s2) 
  
   (if (null? s1) 
     s2 
     (let 
       ((e (car s1))) 
  
       (union-set 
         (cdr s1) 
         (if (element-of-set? e s2) s2 (cons e s2)))))) 
  
 guile> (define element-of-set? member) 
 guile> (define odds '(1 3 5)) 
 guile> (define evens '(0 2 4 6)) 
  
 guile> (union-set '() '()) 
 () 
  
 guile> (union-set '() evens) 
 (0 2 4 6) 
  
 guile> (union-set evens evens) 
 (0 2 4 6) 
  
 guile> (union-set evens odds) 
 (6 4 2 0 1 3 5) 
  
 guile> (union-set odds evens) 
 (5 3 1 0 2 4 6) 
  
 guile> 

Lenatis

 ;;Ex2.59 
  
 (define (union-set s1 s2) 
   (cond ((and (null? s1) (not (null? s2))) 
          s2) 
         ((and (not (null? s1)) (null? s2)) 
          s1) 
         ((element-of-set? (car s1) s2) 
          (union-set (cdr s1) s2)) 
         (else (cons (car s1) 
                     (union-set (cdr s1) s2))))) 
  


Steve Zhang

; used filter to implement the intersection-set and union-set

 (define (filter-intersection-set set1 set2) 
   (filter (lambda (x) (element-of-set? x set2)) set1)) 
  
 (define (filter-union-set set1 set2) 
   (accumulate cons 
               set2 
               (filter (lambda (x) (not (element-of-set? x set2))) 
                       set1))) 
  
  


@bishboria

I thought of this nice solution using adjoin-set instead

  
 (define (union-set set1 set2) 
   (if (null? set1) 
     set2 
     (union-set (cdr set1) (adjoin-set (car set1) set2)))) 


Christian-Delahousse

Here's a solution using append and filter

  
 (define (union s1 s2) 
   (append s1 (filter (lambda (x) 
                        (not (element-of-set? x s1))) 
                      s2))) 


Daniel-Amariei

Iterative and recursive processes.

  
 ;; recursive process 
 (define (union-set A B) 
   (cond ((null? B) A) 
         ((element-of-set? (car B) A) 
          (union-set A (cdr B))) 
         (else (cons (car B) 
                     (union-set A (cdr B)))))) 
  
  
 ;; iterative process 
 (define (union-set-iter A B) 
   (define (iter A B U) 
     (cond ((or (null? B) (null? A)) 
            U) 
           ((element-of-set? (car B) A) 
            (iter A (cdr B) U)) 
           (else (iter A (cdr B) (cons (car B) U))))) 
   (iter A B A)) 


Lambdalef

Short solutions using adjoin-set

  
 (define (union set1 set2) 
   (accumulate adjoin-set set2 set1)) 


smatchcube

Note: be carefull with some of the solutions above, some of them are using the fact that no element appears more than once in set1 or set2 (respecting the representation of sets from the beginning of the chapter). For example bishboria's solution return (0 1 1) for (union-set '(0 0) '(1 1)). That's not really a problem in most cases but we must keep this in mind that we are assuming the input is correct, this is just a little trade-off for better performance.



Sphinxsky

I think this implementation is more complicated but the efficiency will be higher.

  
  
 (define (union-set set1 set2) 
     (define (do-iter set1 set2 result) 
         (cond ((null? set1) result) 
             ((null? set2) set1) 
             (else  
                 (let ((this (car set1))) 
                     (do-iter 
                         (cdr set1) 
                         set2 
                         (if (element-of-set? this set2) 
                             result 
                             (cons this result))))))) 
     (do-iter set1 set2 set2)) 


adsgray

I like the solutions that use accumulate.

My solution is modeled on intersection-set and I think it is iterative. It accumulates into set2. It also assumes that the sets do not permit duplicate entries.

 (define (union-set set1 set2) 
   (cond ((null? set1) set2) 
         ((null? set2) set1) 
         ((element-of-set? (car set1) set2) 
          (union-set (cdr set1) set2)) 
         (else (union-set (cdr set1) (cons (car set1) set2)))))