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