Module Prelude.Multiset

Multiset.Make (Ord) is a set of Ord.t's with repetition.

The order the repetitions of any element is undefined.

A multiset is especially useful for gathering together values that are members of some equivalence class but are not completely identical. Examples would be strings considered case-insensitively, or records compared only on one field. You can add these values to a multiset, and then ask for everything that is equivalent to some value.

Example: gather ints by parity and then find odd ints in the multiset:

module PS = Multiset.Make (struct type t = int let compare = on compare even end)
let ps = 1--10 |> PS.of_list in
PS.find 1 ps = [9; 7; 5; 3; 1]
&& PS.find 5 ps = [9; 7; 5; 3; 1]

You can also use a multiset simply to count repetitions of values:

module PS = Multiset.Make (Int)
(1--3 @ [4;4;4] @ 5--10) |> PS.of_list |> PS.multiplicity 4 = 3

But since a multiset actually stores all the repetitions, it would be more efficient to use Map.Make.incr:

module M = Map.Make (Int)
(1--3 @ [4;4;4] @ 5--10) |> foldr M.incr M.empty |> M.find 4 = 3