## Description

Bags are structures very like sets save that they permit multiple instances as members. Like sets,

order is irrelevant. For example, the following bag contents are permitted:

[�, �, �, �, �, �, �]

and

[�, �, �, �, �, �, �]

Because of this difference between bags and sets, the bag-theoretic operations are somewhat

different from those defined for sets. Here are three of them.

1. Bag-Difference. The operation Bag-Difference when applied to two bags results in a bag

where each element appears as many times as it appears in the first bag, minus the

number of times it appears in the second bag (but never less than 0 times). For example

(bag-difference ‘(a a b a) ‘(b a a)) —>'(a)

(bag-difference ‘(a b a a) ‘(a b c)) —>'(a a)

(bag-difference ‘(a b c) ‘(a b a a)) —>'(c)

(bag-difference ‘(a b c) ‘(a b c)) —>'()

(bag-difference ‘() ‘(a b a a)) —>'()

(bag-difference ‘(a b a a) ‘())—>'(b a a a)

2. Bag-Union. The operation Bag-Union results in a bag that contains the maximum

number elements that are contained in the operands. For example

(bag-union ‘(a a b a) ‘(b a a)) —>'(a b a a)

(bag-union ‘(a b a a) ‘(a b c)) —>'(a a a b c)

(bag-union ‘(a b c) ‘(a b a a)) —>'(c a b a a)

(bag-union ‘(a b c) ‘(a b c)) —>'(a b c)

(bag-union ‘() ‘(a b a a)) —>'(a b a a)

(bag-union ‘(a b a a) ‘())—>'(a b a a)

3. Bag-Intersection. The operation Bag-Intersection results in a bag that contains the

minimum number of elements that are contained in the bag operands. For example

(bag-intersection ‘(a a b a) ‘(b a a)) —> ‘(b a a)

(bag-intersection ‘(a b a a) ‘(a b c)) —> ‘(b a)

(bag-intersection ‘(a b c) ‘(a b a a)) —>'(a b)

(bag-intersection ‘(a b c) ‘(a b c)) —>'(a b c)

(bag-intersection ‘() ‘(a b a a)) —>'()

(bag-intersection ‘(a b a a) ‘())—>'()

The solutions will be turned in by posting a single Racket program (lab07. rkt) containing a

definition of all the functions specified.