bag union


Write three functions computing the union of two bags; one function should take O(n^2) time, one should take O(n log n) time, and the third should take linear time.

 $ cat bu.rkt 
 #lang racket 
  
  
 (define (bag-element-less? e1 e2) 
  
   ; Return #t iff the key in e1 is less than the key in e2. 
    
   (< (car e1) (car e2))) 
  
  
 (define (bag-element-merge e1 e2) 
  
   ; Return a bag element representing the merger of the 
   ; given bag elements.  The keys are assumed to match. 
  
   (cons (car e1) (+ (cdr e1) (cdr e2)))) 
  
  
 (define (bag-sort b) 
  
   ; Return a copy of the given bag with the elements in 
   ; increasing order by key. 
    
   (sort b bag-element-less?)) 
  
  
 (define (bag-union-nsquared b1 b2) 
  
   ; Return the union of the given bags in O(n^2) time. 
    
   (define (find e b) 
  
     (let ((e-key (car e))) 
       (let loop ((b-hd '()) (b-tl b)) 
  
         (if (null? b-tl) 
  
           (values e b) 
  
           (let ((e2 (car b-tl)) 
                 (b-tl (cdr b-tl))) 
  
             (if (eq? e-key (car e2)) 
               (values 
                 (bag-element-merge e e2) 
                 (append b-hd b-tl)) 
  
               (loop (cons e2 b-hd) b-tl))))))) 
  
   (let loop ((b1 b1) (b2 b2) (u '())) 
     (if (null? b1) 
  
       (append b2 u) 
  
       (let ((e (car b1))) 
         (let-values (((e b2) (find e b2))) 
           (loop (cdr b1) b2 (cons e u))))))) 
  
  
 (define (bag-union-nlogn b1 b2) 
  
   ; Return the union of the given bags in O(n log n) time. 
  
   (let loop ((b1 (bag-sort b1)) (b2 (bag-sort b2)) (u '())) 
     (cond 
  
       ((null? b1) 
          (append u b2)) 
  
       ((null? b2) 
          (append u b1)) 
  
       (#t 
         (let ((e1 (car b1)) 
               (e2 (car b2))) 
  
           (cond 
  
             ((bag-element-less? e1 e2) 
               (loop (cdr b1) b2 (cons e1 u))) 
  
             ((bag-element-less? e2 e1) 
               (loop b1 (cdr b2) (cons e2 u))) 
  
             (#t 
              (loop (cdr b1) (cdr b2) (cons (bag-element-merge e1 e2) u))) 
             )))))) 
  
  
 (define (bag-union-linear b1 b2) 
  
   ; Return the union of the given bags in O(n) time. 
  
   (let* 
     ((ht (make-hash)) 
  
      (ht-add (lambda (e) 
                (let ((key (car e))) 
                  (hash-set! ht key (+ (cdr e) (hash-ref ht key 0)))))) 
  
      (ht-add-bag (lambda (b) 
                    (for-each (lambda (e) (ht-add e)) b)))) 
  
     (for-each (lambda (b) (ht-add-bag b)) (list b1 b2)) 
     (hash-map ht (lambda (k v) (cons k v))))) 
  
  
 (require rackunit) 
  
 (for-each 
  
   (lambda (f) 
     (let ((check-same? (lambda (a b c) 
                          (let ((ub (bag-sort (f a b)))) 
                            (check-equal? ub (bag-sort c)) 
                            (check-equal? ub (bag-sort (f b a))))))) 
  
       (check-same? '((1 . 0)) '() '((1 . 0))) 
       (check-same? '((1 . 1)) '((1 . 1)) '((1 . 2))) 
       (check-same? '((1 . 1)) '((2 . 1)) '((1 . 1) (2 . 1))) 
       (check-same? '((1 . 3) (5 . 3) (18 . 3)) '((2 . 3) (18 . 3) (6 . 3)) 
                    '((5 . 3) (18 . 6) (1 . 3) (2 . 3) (6 . 3))))) 
  
   (list bag-union-nsquared bag-union-nlogn bag-union-linear)) 
  
 $ racket bu.rkt  
  
 $