<< Previous exercise (2.61) | Index | Next exercise (2.63) >>

Here's a slightly more elegant solution using ajoint-set from the previous exercise.

;From ex. 2.61 (define (adjoin-set x set) (cond ((null? set) (list x)) ((= x (car set)) set) ((> x (car set)) (cons (car set) (adjoin-set x (cdr set)))) ((< x (car set)) (cons x set)) (else (error "WTF!?")))) ;Answer (define (union-set s1 s2) (cond ((null? s1) s2) ((element-of-set? (car s1) s2) (union-set (cdr s1) s2)) (else (union-set (cdr s1) (adjoin-set (car s1) s2)))))

This solution is not O(n) though. adjoin-set and union-set are O(n). If you call either one for each n, the solution becomes O(n²).

Here's my solution. Is basically the same as the first one, but more elegant.

```
(define (union-set-2 set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
(else
(let ((x1 (car set1))
(x2 (car set2)))
(cons (min x1 x2)
(union-set-2 (if (> x1 x2)
set1
(cdr set1))
(if (> x2 x1)
set2
(cdr set2))))))))
```

racket matching, not as pretty as haskell, but cool anyway

```
(define/match (union-set set1 set2)
[('() set2) set2]
[(set1 '()) set1]
[((list x1 rest1 ...) (list x2 rest2 ...))
(cond [(< x1 x2) (cons x1 (union-set rest1 set2))]
[(< x2 x1) (cons x2 (union-set set1 rest2))]
[else (cons x1 (union-set rest1 rest2))])])
```

I've created a mess ... but it seems to work. It is tail recursive and builds a new resulting list from the two lists / sets. Not sure if tail recursive makes sense here though, since we are building a recursive structure. Anyway, here it is:

```
(define (union-ordered-set set1 set2)
(define (iter result subset1 subset2)
(cond
[(and (empty? subset1) (empty? subset2))
result]
[(empty? subset1)
(cond
[(= (car subset2)(car result)) (iter result subset1 (cdr subset2))]
[else (iter (cons (car subset2) result) subset1 (cdr subset2))])] ; is always the > case, because smaller elements get added first!
[(empty? subset2)
(cond
[(= (car subset1) (car result)) (iter result (car subset1) subset2)]
[else (iter (cons (car subset1) result) (cdr subset1) subset2)])] ; is always the > case
[else ; set1 and set2 are not empty
(cond
[(empty? result) ; initial case
(cond
[(= (car subset1) (car subset2))
(iter (cons (car subset1) result) (cdr subset1) (cdr subset2))]
[(> (car subset1) (car subset2))
(iter (cons (car subset2) result) subset1 (cdr subset2))]
[else ; set1_1 < set2_1
(iter (cons (car subset1) result) (cdr subset1) subset2)])]
[(> (car subset1) (car subset2))
(iter (cons (car subset2) result) subset1 (cdr subset2))]
[(< (car subset1) (car subset2))
(iter (cons (car subset1) result) (cdr subset1) subset2)]
[else ; both first elements are equal
(cond
[(> (car subset1) (car result))
(iter (cons (car subset1) result) (cdr subset1) (cdr subset2))]
[else
(iter result (cdr subset1) (cdr subset2))])])]))
(reverse(iter nil set1 set2)))
```

I know it's ugly. I probably should use a let and avoid a lot of the cars. Here are some unit tests:

```
(test-case
"union-ordered-set test case"
(check-equal?
(union-ordered-set '(1 2 4) '(3))
'(1 2 3 4)
"union-ordered-set does not work correctly")
(check-equal?
(union-ordered-set '(1 2) '(1 3))
'(1 2 3)
"union-ordered-set does not work correctly")
(check-equal?
(union-ordered-set '(2 4 9) '(1 4 9))
'(1 2 4 9)
"union-ordered-set does not work correctly"))
```

```
(define (union-set-2 set1 set2)
(cond ((null? set1) set2) ((null? set2) set1)
(else (let ((a (car set1)) (s1- (cdr set1))
(b (car set2)) (s2- (cdr set2)))
(cond ((< a b) (cons a (union-set-2 s1- (cons b s2-))))
((= a b) (cons a (union-set-2 s1- s2-)))
((< b a) (union-set-2 (cons b s1-) (cons a s2-))))))))
```

the let here is roughly trying to simulate pattern matching. the solution is similar to others, the most unique thing is the line ((< b a) (union-set-2 (cons b s1-) (cons a s2-))) which swaps the first elements of each list so that the smallest element is the car of the first argument, this then activates the (< a b) case on the next call.

Exercise 2.62. Give a Θ(n) implementation of union-set for sets represented as ordered lists.

`(define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) ((= (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) (cdr set2)))) ((< (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2))) (else (cons (car set2) (union-set set1 (cdr set2))))))`

Or, If you want to make it ugly saving 5 car operations on a run,

`(define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) (else (let ((x1 (car set1)) (x2 (car set2))) (cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2)))) ((< x1 x2) (cons x1 (union-set (cdr set1) set2))) (else (cons x2 (union-set set1 (cdr set2)))))))))`