sicp-ex-2.59

[Top Page][Recent Changes][All Pages][Settings][Categories][Wiki Howto]
[Edit][Edit History]

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