# sicp-ex-2.62

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

```

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

```

;From ex. 2.61
(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!?"))))

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

brave one

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

Zelphir

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