package bag

The immutable type of bags.

The empty bag.

Test for emptiness.

occ x b is the number of occurrences of x in bag b. It returns 0 when x is not in b.

mem x b checks whether x belongs to b, i.e. has a multiplicty greater than 0.

add x ?mult b returns a new bag where the multiplicity of x is increased by mult (defaults to one). Raises Invalid_argument if mult is negative.

update x f b returns a bag containing the same elements as b, except for element x whose multiplicity is f (occ x b). Raises Invalid_argument if f returns a negative value.

singleton x is a bag with one element x, with multiplicity 1.

remove x ?mult b returns a new bag where the multiplicity of x is decreased by mult (defaults to one). Raises Invalid_argument if mult is negative.

remove_all x b returns a new bag where the element x is removed.

merge f b1 b2 computes a bag whose elements are a subset of the elements of b1 and of b2. The presence of each such element, and the corresponding multiplicity, is determined with the function f. In terms of the occ operation, we have occ x (merge f b1 b2) = f x (occ x b1) (occ x b2) for any element x, provided that f x 0 0 = 0. Raises Invalid_argument if f returns a negative value.

cardinal b is the sum of the multiplicities.

Returns the list of all elements of the given bag. Each element is given with its multiplicity. The returned list is sorted in increasing order of elements with respect to the ordering over the type of the elements.

Returns the smallest element in the given bag (with respect to the ordering) with its multiplicity, or raises Not_found if the bag is empty.

Returns the smallest element of the given bag (with respect to the ordering) with its multiplicity, or None if the bag is empty.

Returns the largest element in the given bag (with respect to the ordering) with its multiplicity, or raises Not_found if the bag is empty.

Returns the largest element of the given bag (with respect to the ordering) with its multiplicity, or None if the bag is empty.

Returns one element of the given bag with its multiplicity, or raises Not_found if the bag is empty. Which binding is chosen is unspecified, but equal elements will be chosen for equal bags.

Returns one element of the given bag, or None if the set is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal bags.

union b1 b2 returns a new bag b where, for all element x, occ x b = max (occ x b1) (occ x b2).

sum b1 b2 returns a new bag b where, for all element x, occ x b = occ x b1 + occ x b2.

inter b1 b2 returns a new bag b where, for all element x, occ x b = min (occ x b1) (occ x b2).

diff b1 b2 returns a new bag b where, for all element x, occ x b = max 0 (occ x b1 - occ x b2).

Test if two bags are disjoint.

included b1 b2 returns true if and only if, for all element x, occ x b1 <= occ x b2.

iter f b applies f to all elements in bag b. f receives the element as first argument, and its multiplicity as second argument. The elements are passed to f in increasing order with respect to the ordering over the type of the elements.

fold f b a computes (f xN mN ... (f x1 m1 a)...) , where x1 ... xN are the elements in bag b (in increasing order), and m1 ... mN are their multiplicities.

for_all p b checks if all the elements of the bag satisfy the predicate p.

exists p b checks if at least one element of the bag satisfies the predicate p.

filter p b returns the bag with all the elements in b that satisfy predicate p. Multiplicities are unchanged.

partition p b returns a pair of bags (b1, b2), where b1 contains all the elements of b that satisfy the predicate p, and b2 is the bag with all the elements of b that do not satisfy p.

split x b returns a triple (l, m, r), where l is the bag with all the elements of b that are strictly less than x; r is the bag with all the elements of b that are strictly greater than x; m is the multiplicity of x in b.

find_first f b, where f is a monotonically increasing function, returns the lowest element x of b such that f x, or raises Not_found if no such key exists.

find_first_opt f b, where f is a monotonically increasing function, returns an option containing the lowest element x of b such that f x, or None if no such key exists.

find_last f b, where f is a monotonically decreasing function, returns the largest element x of b such that f x, or raises Not_found if no such key exists.

find_last_opt f b, where f is a monotonically decreasing function, returns an option containing the largest element x of m such that f x, or None if no such key exists.

map f b returns a bag with same elements as b, where the multiplicity m of each element of b has been updated by the result of the application of f to m. The elements are passed to f in increasing order with respect to the ordering over the type of the elements. Raises Invalid_argument if f returns a negative value.

Same as Bag.map, but the function receives as arguments both the element and the associated multiplicity. Raises Invalid_argument if f returns a negative value.

Total ordering between bags.

equal b1 b2 tests whether the bags b1 and b2 are equal, that is, contain equal elements with equal multiplicities.

Iterates on the whole bag, in ascending order of elements.

to_seq_from x b iterates on a subset of b, in ascending order of elements, from element x or above.

Adds the given elements to the bag, in order. Raises Invalid_argument if a multiplicity is negative.

Builds a bag from the given elements and multiplicities. Raises Invalid_argument if a multiplicity is negative.