`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(`

to the non-negative integers.
For the purposes of this module, a bag is constructed from two functions:
`B`)

`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 well-formed 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(`

, but commits to the first solution it finds. For example, if`Pred`,`Bag`)`p(X,X,_)`

,`somechk(p(X),`

would be an analogue of`Bag`)`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 proper list

`List`to a`Bag`representing the same multi-set. 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 multi-set 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 multi-set 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, sobag_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 left-most 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 left-most is returned.`bag_max/3`

breaks ties the same way, sobag_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 multi-set`Bag`(the sum of the multiplicities of its elements) and`SetCardinality`with the number of distinct elements. `make_sub_bag(`

`+Bag`,`-SubBag`)-
enumerates the sub-bags of

`Bag`, unifying`SubBag`with each of them in turn. The order in which the sub-bags are generated is such that if SB2 is a sub-bag of SB1 which is a sub-bag 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 sub-bag 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 multi-set 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 multi-set 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 multi-set intersection of bags`Bag1`and`Bag2`. `bag_intersection(`

`+ListOfBags`,`-Intersection`)-
is true when

`ListOfBags`is given as a non-empty 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 multi-sets

`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.