10.5 Bags, or Multisets—library(bags)
This library module provides operations on bags.
Bags are also known as multisets.
A bag B is a function from a set dom(
B)
to the nonnegative integers.
For the purposes of this module, a bag is constructed from two functions:
bag
 creates an empty bag
bag(
E,
M,
B)
 extends the bag B with a new element E which occurs
with multiplicity M, and which precedes all elements of B
in Prolog's order.
A bag is represented by a Prolog term mirroring its construction. There
is one snag with this: what are we to make of
bag(f(a,Y), 1, bag(f(X,b), 1, bag)) ?
As a term it has two distinct elements, but f(a,b)
will be reported as
occurring in it twice. But according to the definition above,
bag(f(a,b), 1, bag(f(a,b), 1, bag))
is not the representation of any bag, that bag is represented by
bag(f(a,b), 2, bag)
alone. We are apparently stuck with a scheme which is only guaranteed
to work for "sufficiently instantiated" terms, but then, that's true of
a lot of Prolog code.
The reason for insisting on the order is to make union and
intersection linear in the sizes of their arguments.
library(ordsets)
does the same for ordinary sets.
Exported predicates:
is_bag(
+Bag)

recognises proper wellformed bags. You can pass variables to
is_bag/1
,
and it will reject them.
portray_bag(
+Bag)

writes a bag to the current output stream in a pretty form so that
you can easily see what it is. Note that a bag written out this
way can not be read back in. For that, use
write_canonical/1
.
The point of this predicate is
to have bags displayed nicely by print/1 and the debugger.
This will print things which are not fully instantiated, which is
mainly of interest for debugging this module.
checkbag(
:Pred,
+Bag)

is true when Bag is a Bag{E1:M1, ..., En:Mn} with elements Ei
of multiplicity Mi, and Pred(Ei, Mi) is true for each i.
mapbag(
:Pred,
+Bag)

is true when Bag is a Bag{E1:M1, ..., En:Mn} with elements Ei
of multiplicity Mi, and Pred(Ei) is true for each element Ei.
The multiplicities are ignored: if you don't want this, use
checkbag/2
.
mapbag(
:Pred,
+OldBag,
NewBag)

is true when OldBag is a Bag{E1:M1, ..., En:Mn} and NewBag is a
Bag{F1:M'1, ..., Fn:M'n} and the elements of OldBag and NewBag
are related by Pred(Ei, Fj). What happens is that the elements
of OldBag are mapped, and then the result is converted to a bag,
so there is no positional correspondence between Ei and Fj.
Even when Pred is bidirectional,
mapbag/3
is not. OldBag should
satisfy is_bag/1
before mapbag/3
is called.
somebag(
:Pred,
+Bag)

is true when Bag is a Bag{E1:M1, ..., En:Mn} with elements Ei of
multiplicity Mi and Pred(Ei, Mi) is true of some element Ei and
its multiplicity. There is no version which ignores the Mi.
somechkbag(
:Pred,
+Bag)

is like
somebag(
Pred,
Bag)
, but commits to the first solution it
finds. For example, if p(X,X,_)
, somechk(p(X),
Bag)
would be an
analogue of memberchk/2
for bags.
bag_to_list(
+Bag,
List)

converts a Bag{E1:M1, ..., En:Mn} to a list where each element
appears as many times as its multiplicity requires. For example,
Bag{a:1, b:3, c:2}
would be converted to [a,b,b,b,c,c]
.
bag_to_ord_set(
+Bag,
Ordset)

converts a Bag{E1:M1, ..., En:Mn} to a list where each element
appears once without its multiplicity. The result is always an
ordered (representation of a) set, suitable for processing by
library(ordsets)
. See also bag_to_list/2
.
bag_to_ord_set(
+Bag,
+Threshold,
Ordset)

given a Bag{E1:M1, ..., En:Mn} returns a list in standard order of
the set of elements {Ei  Mi >= Threshold}. The result is an Ordset.
list_to_bag(
+List,
Bag)

converts a List to a Bag representing the same multiset.
Each element of the List appears once in the Bag together
with the number of times it appears in the List.
bag_to_set(
+Bag,
Set)

converts a Bag{E1:M1, ..., En:Mn} to a list which represents the
Set {E1, ..., En}. The order of elements in the result is not
defined: for a version where the order is defined use
bag_to_ord_set/2
.
bag_to_set(
+Bag,
+Threshold,
Set)

given a Bag{E1:M1, ..., En:Mn} returns a list which represents the
Set of elements {Ei  Mi >= Threshold}. Because the Bag is sorted,
the result is necessarily an ordered set.
empty_bag(
?Bag)

is true when Bag is the representation of an empty bag. It can be
used both to make and to recognise empty bags.
member(
?Element,
?Multiplicity,
+Bag)

is true when Element appears in the multiset represented by Bag
with the indicated Multiplicity. Bag should be instantiated,
but Element and Multiplicity may severally be given or solved for.
memberchk(
+Element,
?Multiplicity,
+Bag)

is true when Element appears in the multiset represented by Bag,
with the indicated Multiplicity. It should only be used to check
whether a given element occurs in the Bag, or whether there is an
element with the given Multiplicity. Note that guessing the
multiplicity and getting it wrong may force the wrong choice of
clause, but the result will be correct if
is_bag(
Bag)
.
bag_max(
+Bag,
CommonestElement)

unifies CommonestElement with the element of Bag which occurs
most often, picking the leftmost element if several have this
multiplicity. To find the multiplicity as well, use
bag_max/3
.
bag_max/2
and bag_min/2
break ties the same way.
bag_min(
+Bag,
RarestElement)

unifies RarestElement with the element of Bag which occurs
least often, picking the leftmost element if several have this
multiplicity. To find the multiplicity as well, use
bag_min/3
.
bag_max/2
and bag_min/2
break ties the same way, so
bag_max(Bag, Elt), bag_min(Bag, Elt)
is true only when all the elements of Bag have the same multiplicity.
bag_max(
+Bag,
CommonestElement,
Multiplicity)

unifies CommonestElement with the element of Bag which occurs
most often, and Multiplicity with the multiplicity of that element.
If there are several elements with the same greatest multiplicity,
the leftmost is returned.
bag_min/3
breaks ties the same way.
bag_min(
+Bag,
RarestElement)

unifies RarestElement with the element of Bag which occurs
least often, and Multiplicity with the multiplicity of that element.
If there are several elements with the same least multiplicity,
the leftmost is returned.
bag_max/3
breaks ties the same way, so
bag_max(Bag, Elt, Mult), bag_min(Bag, Elt, Mult)
is true only when all the elements of Bag have multiplicity Mult.
length(
+Bag,
BagCardinality,
SetCardinality)

unifies BagCardinality with the total cardinality of the multiset
Bag (the sum of the multiplicities of its elements) and
SetCardinality with the number of distinct elements.
make_sub_bag(
+Bag,
SubBag)

enumerates the subbags of Bag, unifying SubBag with each of them in
turn. The order in which the subbags are generated is such that if
SB2 is a subbag of SB1 which is a subbag of Bag, SB1 is generated
before SB2. In particular, Bag is enumerated first and bag last.
test_sub_bag(
+Bag,
+SubBag)

is true when SubBag is (already) a subbag of Bag. That is,
each element of SubBag must occur in Bag with at least the
same multiplicity. If you know SubBag, you should use this
to test, not
make_sub_bag/2
.
bag_union(
+Bag1,
+Bag2,
Union)

unifies Union with the multiset union of bags Bag1 and Bag2.
bag_union(
+ListOfBags,
Union)

is true when ListOfBags is given as a proper list of bags and Union
is their multiset union. Letting K be the length of ListOfBags,
and N the sum of the sizes of its elements, the cost is
O(N lg K).
bag_intersection(
+Bag1,
+Bag2,
Intersection)

unifies Intersection with the multiset intersection
of bags Bag1 and Bag2.
bag_intersection(
+ListOfBags,
Intersection)

is true when ListOfBags is given as a nonempty proper list of Bags
and Intersection is their intersection. The intersection of an
empty list of Bags would be the universe with infinite multiplicities!
bag_intersect(
+Bag1,
+Bag2)

is true when the multisets Bag1 and Bag2 have at least one
element in common.
bag_add_element(
+Bag1,
+Element,
+Multiplicity,
Bag2)

computes Bag2 = Bag1 U {Element:Multiplicity}.
Multiplicity must be an integer.
bag_del_element(
+Bag1,
+Element,
+Multiplicity,
Bag2)

computes Bag2 = Bag1 \ {Element:Multiplicity}.
Multiplicity must be an integer.
bag_subtract(
+Bag1,
+Bag2,
Difference)

is true when Difference is the multiset difference of Bag1 and Bag2.
Send feedback on this subject.