package bag

Bags (aka multisets).

A bag is merely a map that binds each element to its multiplicity in the bag (see function occ below).

Caveat: Bags are internally implemented with AVLs (from module Map) and thus there is no unicity of representation. Consequently, the polymorphic equality (=) must not be used on bags. Functions compare and equal are provided to compare bags.

Similarly, the polymorphic hash function Hashtbl.hash must not be used on bags. If one intends to use bags as hash table heys, a suitable hash function must be defined, with something like

let hash b =
  fold (fun x n h -> 5003 * (5003 * h + hash x) + n) b 0

where hash is a suitable hash function for the bag elements.