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