package bag

  1. Overview
  2. Docs
package bag
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module BagSource

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.

Sourcemodule Make (X : sig ... end) : sig ... end