package bitvec-order

Provides comparators for use with Janestreet Libraries.

A comparator is a comparison function paired with a type that is unique to this function and that acts as the witness of equality between two comparison functions.

Comparators are extensively used in the Janestreet's suite of libraries, e.g., Base, Core_kernel@@warning "-D", Core, etc. Comparators are used to create sets, maps, hashtables, to instantiate interfaces, and algorithms that require comparison.

This module provides two comparators, ascending and descending, which represent two corresponding orderings, as well as the natural comparator, which is the default ordering that equals with the ascending order, which should be used in cases where a particular ordering doesn't matter.

This library interface is designed from the point of view of the library user, to minimize verbosity and maximize readability and the ease of use.

For example, an empty set is created as

let words = Set.empty Bitvec_order.natural

,

and it has type

(Bitvec.t,Bitvec_order.natural) set

(See the note on comparators below for the old style comparators)

This module also provides (implements) the Base.Comparator.S interface that is required by a few Janestreet functors, in particular, you can construct the type of a set of bitvectors, as

type t = Set.M(Bitvec_oder)

, or for a mapping from bitvectors to OCaml int it would be

type t = int Map.M(Bitvec_order)

And to instantiate the Comparable.S interface,

nclude Comparable.Make(Bitvec_order).

See also, Bitvec_binprot that provide support for the binable interfaces.

Finally, for even more concise and readable syntax we provide the Comparators module that designed to be opened, since it defines properly prefixed identifiers, which will unlikely clash with any existing name, so that the above examples could be expressed

open Bitvec_order.Comparators
let words = Set.empty bitvec_order
type words = (bitvec, bitvec_order) Set.t
let decreasing x y = bitvec_descending.compare x y

The old style comparators

Historically, the comparator in the Janestreet libraries had two representations - as a record that contains the compare function, and as a module that contains this record and an instance of the witness type. The former representation is mostly used for internal purposes, while the latter is expected in most of the public functions, like Set.empty, Map.empty in the form of the first-class module, or in different Make* functors. In this library, when we use the word comparator to refer to the latter representation, i.e., to the module. When the underlying comparator record is needed, it could be obtained through the comparator field of the module.

The older versions of Core and Base libraries were accepting the comparator as a record, so instead of writing

Set.empty Bitvec_order.natural

the following notation should be used

Set.empty Bitvec_order.Natural.comparator

compare x y orders x and y in the natural order.

type index for the increasing order

type index for the decreasing order

we use the increasing order as the natural ordering

a type abbreviation for a comparator packed into a module.

See the note about the historical meaning of the word comparator.

natural the packed comparator that sorts in the natural order

ascending the packed comparator that sorts in the increasing order

descending the packed comparator that sorts in the decreasing order

natural the comparator that sorts in the natural order

natural the comparator that sorts in the natural order

natural the comparator that sorts in the natural order

Open this module to make the following fields available