BatOrd
type order =
type 'a ord = 'a -> 'a -> order
The type of ordering functions returning an order
variant.
The legacy int-returning comparisons :
module type Comp = sig ... end
We use compare
as member name instead of comp
, so that the Comp modules can be used as the legacy OrderedType interface.
module type Ord = sig ... end
val ord0 : int -> order
val comp0 : order -> int
val poly_comp : 'a comp
val poly_ord : 'a ord
val poly : 'a ord
Polymorphic comparison functions, based on the Pervasives.compare
function from inria's stdlib, have polymorphic types: they claim to be able to compare values of any type. In practice, they work for only some types, may fail on function types and may not terminate on cyclic values.
They work by runtime magic, inspecting the values in an untyped way. While being an useful hack for base types and simple composite types (say (int * float) list
, they do not play well with functions, type abstractions, and structures that would need a finer notion of equality/comparison. For example, if one represent sets as balanced binary tree, one may want set with equal elements but different balancings to be equal, which would not be the case using the polymorphic equality function.
When possible, you should therefore avoid relying on these polymorphic comparison functions. You should be especially careful if your data structure may later evolve to allow cyclic data structures or functions.
Reverse a given ordering. If Int.ord
sorts integer by increasing order, rev Int.ord
will sort them by decreasing order.
The type for equality function.
All ordered types also support equality, as equality can be derived from ordering. However, there are also cases where elements may be compared for equality, but have no natural ordering. It is therefore useful to provide equality as an independent notion.
val eq_ord0 : order -> bool
module type Eq = sig ... end
min ord
will choose the smallest element, according to ord
. For example, min Int.ord 1 2
will return 1
.
(* the minimum element of a list *)
let list_min ord = List.reduce (min ord)
binary lifting of the comparison function, using lexicographic order: bin_ord ord1 v1 v1' ord2 v2 v2'
is ord2 v2 v2'
if ord1 v1 v1' = Eq
, and ord1 v1 v1'
otherwise.
These functions extend an existing equality/comparison/ordering to a new domain through a mapping function. For example, to order sets by their cardinality, use map_ord Set.cardinal Int.ord
. The input of the mapping function is the type you want to compare, so this is the reverse of List.map
.
module Incubator : sig ... end