Here's a solution using append and filter
(define (union s1 s2)
(append s1 (filter (lambda (x)
(not (element-of-set? x s1)))
s2)))
<< 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>
; 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)))
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))))
Here's a solution using append and filter
(define (union s1 s2)
(append s1 (filter (lambda (x)
(not (element-of-set? x s1)))
s2)))
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))
Short solutions using adjoin-set
(define (union set1 set2)
(accumulate adjoin-set set2 set1))
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.
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))
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)))))
Lenatis