; union of two bags
(define bag1 '((#\e . 3) (#\r . 3) (#\a . 3)))
(define bag2 '((#\b . 3) (#\r . 3) (#\f . 3)))
(define (update x xs)
(let loop ((xs xs) (zs (list)))
(if (null? xs) (cons x zs)
(if (char=? (car x) (caar xs))
(append (cdr xs) zs (list (cons (car x) (+ (cdr x) (cdar xs)))))
(loop (cdr xs) (cons (car xs) zs))))))
(define (union1 bag1 bag2)
(let loop ((bag1 bag1) (bag2 bag2))
(if (null? bag1) bag2 (loop (cdr bag1) (update (car bag1) bag2)))))
(display (union1 bag1 bag2)) (newline)
(define (union2 bag1 bag2)
(define (lt? a b) (char<? (car a) (car b)))
(let loop ((xs (sort (append bag1 bag2) lt?)) (zs (list)))
(if (null? xs) zs
(if (null? zs) (loop (cdr xs) (cons (car xs) zs))
(if (char=? (caar xs) (caar zs))
(loop (cdr xs) (cons (cons (caar xs)
(+ (cdar xs) (cdar zs))) (cdr zs)))
(loop (cdr xs) (cons (car xs) zs)))))))
(display (union2 bag1 bag2)) (newline)
(define (union3 bag1 bag2)
(let ((ht (make-hashtable)))
(do ((xs (append bag1 bag2) (cdr xs)))
((null? xs)
(vector->list
(let-values (((ks vs) (hashtable-entries ht)))
(vector-map cons ks vs))))
(hashtable-update! ht (caar xs)
(lambda (x) (+ x (cdar xs))) 0))))
(display (union3 bag1 bag2))