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


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))) 
           (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) 
           (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 
 (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!?")))) 
 (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) 
           (let ((x1 (car set1)) 
                 (x2 (car set2))) 
             (cons (min x1 x2) 
                   (union-set-2 (if (> x1 x2) 
                                  (cdr set1)) 
                                (if (> x2 x1) 
                                  (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))])]) 


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) 
       [(and (empty? subset1) (empty? subset2)) 
       [(empty? subset1) 
           [(= (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) 
           [(= (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 
           [(empty? result)  ; initial case 
               [(= (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 
               [(> (car subset1) (car result)) 
                 (iter (cons (car subset1) result) (cdr subset1) (cdr subset2))] 
                 (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:

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