sicp-ex-2.59


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> 

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


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.