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

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