A bag (also called a multiset) is much like a set except that it associates with each element a natural number (nonnegative integer) called the multiplicity, which represents the number of occurrences of the element in the bag. So, for instance, if you start with an empty bag and add an element to it twice, the resulting bag will contain that element with multiplicity 2. Removing the same element once leaves it in the bag with multiplicity 1.
The basics should be familiar by now (once you get used to the print syntax, at least; the #%
inclusions are for elements with multiplicity greater than 1):
> (empty-bag)
##{% %}
> (defparameter b1 (bag 1 2 1))
B1
> b1
##{% #%(1 2) 2 %}
> (with b1 3)
##{% #%(1 2) 2 3 %}
> (less b1 1)
##{% 1 2 %}
> (bag ($ b1) 2 3)
##{% #%(1 2) #%(2 2) 3 %}
> (defparameter b2 (bag 2 2 3))
B2
> b2
##{% #%(2 2) 3 %}
> (union b1 b2)
##{% #%(1 2) #%(2 2) 3 %}
> (intersection b1 b2)
##{% 2 %}
> (bag-sum b1 b2)
##{% #%(1 2) #%(2 3) 3 %}
> (bag-product b1 b2)
##{% #%(2 2) %}
> (size b1)
3
> (set-size b1)
2
union and intersection take the max and min of the multiplicities of
each element, respectively; bag-sum and bag-product take their sum and product. The
standard operation size returns the total multiplicity; to get the number of unique elements,
use set-size.