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 $