Module Multiset.Make

The type of the multiset elements.

The type of multisets.

The empty set.

The comparison function for elt's.

compare is the version of compare for multisets.

(support t) is the list of all the distinct (under Ord.compare) elements of the multiset t.

Note that each of the elements in the result is an arbitrary exemplar of its equivalent repetitions.

support is equivalent to (to_list >> sort_uniq Ord.compare) but is faster.

(support_size) is (len << support) but is faster.

(cardinal t) is the sum of the multiplicities of all the elements of t.

size is cardinal.

(multiplicity elt t) is the number of repetitions of elt in t.

count is multiplicity.

(is_empty t) is true iff t is empty.

(mem x t) is true iff x is a member of t

(disjoint a b) is true iff a and b have no elements in common.

(equal a b) is true iff both multisets contain the same elements, and the same repetitions of elements.

(subset a b) is true iff all the distinct elements of a are contained in b, and the multiplicity of each element of a is <= the multiplicity of the corresponding element of b.

(for_all p t) is true iff all elements of t satisfy the predicate p.

(exists p t) is true iff at least one element of t satisfies the predicate p.

(singleton elt) is the multiset that contains only elt.

(of_list xs) is the multiset containing containing all the elements of xs.

(split x t) is a triple (l, present, r), where l is the multiset of elements of t that are strictly less than x; r is the multiset of elements of t that are strictly greater than x; present is false if t contains no element equal to x, or true if t contains an element equal to x.

If you also need the repetitions of x, you can call (find x t).

(add elt t) is the multiset t with elt added.

Invariant: (multiplicity elt (add elt t)) = (1 + multiplicity elt t)

(addwith f) is (fun f x t -> add (f x) t).

(addwhen p x t) is (add x t) when p x = true and otherwise is t.

(remove elt t) is the multiset that contains all the elements of t excepting elt.

All repetitions of elt are removed.

Invariants:

• (mem x (remove x t)) = false
• (multiplicity x (remove x t)) = 0

(replace elt reps t) is t with all the repetitions of elt replaced by reps.

(iter f t) iterates f across each distinct element of t; the repetitions of each element are given to f as a list.

(flatiter f t) iterates f over all the repetitions of all the elements of t.

flatiter f is equivalent to (iter (List.iter f)).

(map f t) is a multiset where all repetitions of all elements have been replaced by the result of applying f to those elements.

(flatfold f t init) computes (f xⁿ ... (f x² (f x¹ init))...), where x¹ ... xⁿ are the repetitions of all elements of t, in increasing order.

(fold f t init) is like flatfold except that f is called once for each distinct distinct element of t, and f receives the repetitions of an element as a list.

(filter p t) is the multiset of all elements that satisfy the predicate p.

p is applied to each repetition of each distinct element.

(partition p t) returns a pair of multisets (t1, t2), where t1 is the multiset of all the elements of t that satisfy the predicate p, and t2 is the multiset of all the elements of t that do not satisfy p.

(union s t) is the maximum or lowest common multiple of multisets s and t.

See sum for what seems to me a more practical function.

(sum s t) is the disjoint union of s and t.

The sum contains the union of the distinct elements of s and t, and the repetitions of each element is the union of its repetitions in the two original sets..

Invariants:

• (support (sum s t)) = List.union (support s) (support t)
• (sort Ord.compare (elements (sum s t))) = sort Ord.compare (elements s @ elements t)

(inter s t) is the infimum or greatest common divisor of multisets s and t.

(diff s t) is the multiset that contains the distinct elements of s that are not in t.

(find elt t) is the list of the repetitions of elt in t.

Invariant: (len (default [] (find elt) t)) = (multiplicity elt t)

• raises Not_found

  if is_empty t

(find_opt elt t) is (catch ~this:Not_found (find elt) t).

(elements t) are all the repetitions of all the distinct elements of t, in ascending order of Ord.compare.

Invariant:

• len (support t) <= len (elements t)

(to_list t) is elements.

(repetitions t) is the list of all repetitions of each distinct element, in ascending order of Ord.compare, in the form of a list of lists.

Invariants:

• (len << repetitions) = (len << support)
• (repetitions >> List.map len >> List.sum) = cardinal
• flatten (repetitions t) = elements t

(choose t) is the set of repetitions of one distinct element of the given multiset. Which element is chosen is unspecified, but equal elements will be chosen for equal multisets.

• raises Not_found

  if is_empty t

(choose t) is the set of repetitions of one distinct element of the given multiset; if the multiset is empty, the result is None. Which element is chosen is unspecified, but equal elements will be chosen for equal multisets.

(find_first f t) where f is a monotonically increasing function, returns the repetitions of the lowest element e of t such that (f e).

• raises Not_found

  if no such element exists.

(find_first_opt f) is (catch (find_first_opt f)).

(find_last f t) where f is a monotonically decreasing function, returns the repetitions of the highest element e of t such that (f e).

• raises Not_found

  if no such element exists.

(find_last_opt f) is (catch (find_last_opt f)).

(min_elt_opt t) is the smallest element of t, per Ord.compare.

• raises Not_found

  if no such element exists.

(min_elt f) is (catch (min_elt f)).

(max_elt_opt t) is the largest element of t, per Ord.compare.

• raises Not_found

  if no such element exists.

(max_elt_opt f) is (catch (max_elt f)).

(to_seq t) is the Seq.t equivalent to (repetitions t).

(to_seq_from elt t) is (to_seq t) but containing only those elements from elt or above.

(of_seq seq) is the multiset containing all the elements of seq.

(add_seq seq t) is t with the addition of all the elements in seq.

(to_string ?(sep=", ") f t) returns a string representation of the multiset t, where the string representation of each elt is given by f.

(print ?sep f t) is (to_string ?sep f t |> print_endline).

(random ?size r ()) is a random multiset of size (size ()) (default: < 100), and each element is given by (r ()).