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

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

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

 (define (union-set-2 set1 set2) 
   (cond ((null? set1) set2) ((null? set2) set1) 
         (else (let ((a (car set1)) (s1- (cdr set1)) 
                     (b (car set2)) (s2- (cdr set2))) 
                 (cond ((< a b) (cons a (union-set-2 s1- (cons b s2-)))) 
                       ((= a b) (cons a (union-set-2 s1- s2-))) 
                       ((< b a) (union-set-2 (cons b s1-) (cons a s2-)))))))) 

the let here is roughly trying to simulate pattern matching. the solution is similar to others, the most unique thing is the line ((< b a) (union-set-2 (cons b s1-) (cons a s2-))) which swaps the first elements of each list so that the smallest element is the car of the first argument, this then activates the (< a b) case on the next call.