A bag, also called a multiset, is an unordered collection of values that permits duplicates. Each element of the bag has an associated multiplicity (sometimes called “count”), which is a positive integer specifying the number of repetitions of the element in the bag. As with a set, there are efficient operations to add a specified number of repetitions of a value, to remove a specified number of repetitions, to test whether the bag contains a value, and to retrieve the multiplicity of a value. Adding a value to a bag that already contains it adds the specified number of repetitions to its multiplicity; removing subtracts the number of repetitions removed, but once all repetitions are removed, further removals have no effect (multiplicities are never negative).
Although bags are conceptually unordered, FSet imposes an order for its own purposes. The WB implementation allows you to control this ordering.
There are two ways to iterate over bags: as single elements with each element repeated a number of times equal to its multiplicity, or as pairs of an element and its multiplicity.
Many of the bag operations accept a set in place of a bag, treating it as a bag where every element has multiplicity 1.
The default implementation of bags is currently CHAMP (ch-bag). The WB implementation
(wb-bag) is also available.
The abstract class for FSet functional bags. Subclass of collection.
Returns true iff x is an FSet functional bag.
The abstract class for FSet transient bags. Subclass of transient-collection.
Returns true iff x is an FSet transient bag.
Constructor function. Returns an empty bag of the default implementation, currently ch-bag,
and the default organization.
Constructor macro. Constructs a bag of the default implementation, currrenlty ch-bag, and
the default organization, according to the supplied argument subforms. Each argument subform can be
an expression, whose value will be added to the bag with multiplicity 1; or a list of the form
($ expression), in which case the expression must evaluate to a bag (or a set), whose
elements are added to the result bag with the specified multiplicities (1, if it’s a set); or a list
of the form (% value multiplicity), which adds the value to the bag with the
specified multiplicity.
Functional bags implemented using CHAMP trees. Subclass of bag. These print as:
##{% e0 #%(e1 m1) ... %}[compare-fn]
Note the double #, which indicates CHAMP. Elements with multiplicity 1 are printed
unadorned; elements with higher multiplicity are printed followed by their multiplicity, wrapped in
#%(…). The comparison function is printed only if it is not compare.
Returns true iff x is an FSet functional CHAMP bag.
Constructor function. Returns an empty ch-bag. By default, it will be ordered by compare.
To use a custom ordering, supply the comparison function name (a symbol) as compare-fn-name;
a hash function must have been defined for it using define-hash-function.
Constructor macro. Constructs a ch-bag according to the supplied argument subforms. See
bag, above for the interpretation of subforms.
Constructor macro. Constructs a ch-bag with a custom organization, according to the supplied
argument subforms. compare-fn-name must be a symbol naming the desired comparison function;
a hash function must have been defined for it using define-hash-function. See bag, above for the interpretation of
subforms.
Functional bags implemented using WB-trees. Subclass of bag. These print as:
#{% e0 #%(e1 m1) ... %}[compare-fn]
Note the single #, which indicates WB. Elements with multiplicity 1 are printed unadorned;
elements with higher multiplicity are printed followed by their multiplicity, wrapped in
#%(…). The comparison function is printed only if it is not compare.
Returns true iff x is an FSet functional WB-tree bag.
Constructor function. Returns an empty wb-bag. By default, it will be ordered by compare.
To use a custom ordering, supply the comparison function name (a symbol) as compare-fn-name;
a hash function must have been defined for it using define-hash-function.
Constructor macro. Constructs a wb-bag according to the supplied argument subforms. See
bag, above for the interpretation of subforms.
Constructor macro. Constructs a wb-bag with a custom organization, according to the supplied
argument subforms. compare-fn-name must be a symbol naming the desired comparison function.
See bag, above for the interpretation of subforms.