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 non-negative 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 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(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 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, 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 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, 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 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.