Module Order

Functionality for comparison and ordering of OCaml values.

Ordering

Ordering values are produced by comparators - functions that compare two values. Comparators for common data types can be found in the Comparator module.

The complementary Ordering module includes operations on ordering values.

Examples

open Order

(* 2 < 2 *)
let compare = Comparator.int in
assert (is Less (compare 1 2));

(* [1; 2] = [1; 2] *)
let compare = Comparator.(list int) in
assert (is Equal (compare [1; 2]));

(* (42, "abc") > (42, "def") *)
let compare = Comparator.(pair int string) in
assert (is Greater (compare (42, "abc") (42, "def")));
type ordering = [
| `Less
| `Equal
| `Greater
]

Defines the relative ordering of two values.

module Ordering : sig ... end

Module for the Ordering type.

Equality

Equality comparisons for monomorphic and polymorphic types.

This module defines interfaces and operations for equality comparison between values. Equality is an equivalence relation, which means that it must be: reflexive, symmetric and transitive.

User-defined types can implement the Equal0, Equal1 or Equal2 interfaces (according to the arity of the main type) to include specialized equality comparison functions.

Note: The extended version of Equal for polymorphic types does not include infix functions since they are only useful with two arguments and Equal1 and Equal2 would require extra arguments for each type parameter.

Examples

open Order

module Book = struct
  type t = {
    title : string;
    author : string;
    isbn : int;
  }

  (* Equality by ISBN. *)
  include Equal0.Extend(struct
    type nonrec t = t

    let equal t1 t2 =
      Equality.string t1.isbn t2.isbn
  end)
end

Equality functions

type 'a equality = 'a -> 'a -> bool

The type of equality testing functions.

module Equality : sig ... end

Module for the Ordering function type. Includes implementations for common data types.

Monomorphic Types

Equality comparisons for monomorphic types, like integers and strings.

module type Equal0 = sig ... end

Base interface for equatable monomorphic types.

module Equal0 : sig ... end

Extension builder module for equatable monomorphic types.

Polymorphic Unary Types

Equality comparisons for polymorphic unary types, like lists and option values.

module type Equal1 = sig ... end

Base interface for equatable polymorphic unary types.

module Equal1 : sig ... end

Extension builder module for equatable monomorphic types.

Polymorphic Binary Types

Equality comparisons for polymorphic binary types, like results or either types.

module type Equal2 = sig ... end

Base interface for equatable polymorphic binary types.

module Equal2 : sig ... end

Extension builder module for equatable monomorphic types.

Default Aliases

module type Equal = Equal0

Alias for extended interface for equatable monomorphic types.

module Equal = Equal0

Alias for interface builder for equatable monomorphic types.

Comparisons

This section defines types, interfaces and operations for values that form a total order relation.

An order is a total order if it is (for all a, b and c):

  • total and antisymmetric: exactly one of a < b, a = b or a > b is true;
  • transitive, a < b and b < c implies a < c. The same must hold for = and >.

User-defined types can implement the Ordered0, Ordered1 or Ordered2 interfaces (based on to the arity of the main type) to included a specialized comparison functions.

Example

open Order

module Person = struct
  type t = {
    name : string;
    age : int;
  }

  (* Ordering by age. *)
  module By_age = Ordered0.Extend(struct
    type nonrec t = t

    let compare t1 t2 =
      Comparator.int t1.age t2.age
  end)
end

let alice = Person.{ name = "Alice"; age = 23 }
let bob   = Person.{ name = "Bob";   age = 28 }
let craig = Person.{ name = "Craig"; age = 43 }

let () =
  assert Person.By_age.(bob > alice);
  assert Person.By_age.(max bob craig = craig);
  assert Person.By_age.(bob |> between ~min:alice ~max:craig)

Comparison functions

type 'a comparator = 'a -> 'a -> ordering

The type of order comparison functions.

Multiple comparators can be composed to handle complex polymorphic types. The Comparator module defines comparison functions for common monomorphic and polymorphic types and can be used for that.

Examples

An arrays of optional pairs with ints and strings can be compared with:

let my_compare =
  Comparator.(array (option (pair int string)))

let () =
  let a1 = [|Some (42, "foo"); Some (43, "bar"); Some (100, "a")|] in
  let a2 = [|Some (42, "foo"); Some (10, "baz"); None|] in

  (* a1 is greater than a2 because the nested 43 is greater than 10. *)
  assert (is Greater (my_compare a1 a2));

  (* The composed comparator can also be used inline: *)
  assert (is Less Comparator.(array (option (pair int string)) a2 a1))
module Comparator : sig ... end

Module for the comparator function type. Includes implementations for common data types.

Monomorphic Types

Ordering comparisons for monomorphic types.

module type Ordered0 = sig ... end

Base interface for ordered types.

module Ordered0 : sig ... end

Extension builder module for ordered monomorphic types.

Polymorphic Unary Types

Ordering comparisons for polymorphic unary types.

module type Ordered1 = sig ... end

Base interface for ordered types.

module Ordered1 : sig ... end

Extension builder module for ordered polymorphic unary types.

Polymorphic Binary Types

Ordering comparisons for polymorphic binary types.

module type Ordered2 = sig ... end

Base interface for ordered types.

module Ordered2 : sig ... end

Extension builder module for ordered polymorphic binary types.

Default Aliases

module type Ordered = Ordered0

Alias for extended interface for ordered monomorphic types.

module Ordered = Ordered0

Alias for interface builder for ordered monomorphic types.

Physical Equality

val is : 'a -> 'a -> bool

is a b tests for physical equality of a and b.

On mutable types such as references, arrays, byte sequences, records with mutable fields and objects with mutable instance variables, is a b is true if and only if physical modification of a also affects b. On non-mutable types, the behavior of is is implementation-dependent; however, it is guaranteed that is a b implies a = b.

To check if two values are physically distinct use not (is a b).

val (==) : [ `Deprecated of 'a -> 'a -> bool ]

Using the == is discouraged because of its visual similarity with = and different semantics. The is operator should be used instead.

Note: This operator is included to raise a deprecation warning during compilation.

Monomorphic Comparison

Public comparison operations included when the top-level Order module is open.

By default the standard comparison functions are specialized to integers. To compare other types consider using the combinators provided in the Equality and Comparator modules. Alternatively you may consider opening the Magic module.

val compare : int -> int -> ordering

Produces the ordering between two integers.

val (=) : int -> int -> bool

a = b tests if the integers a and b are equal.

val (<>) : int -> int -> bool

a <> b tests if the integers a and b are not equal.

val (<) : int -> int -> bool

a < b tests if the integer a is less than b.

val (>) : int -> int -> bool

a > b tests if the integer a is greater than b.

val (<=) : int -> int -> bool

a <= b tests if the integer a is less than or equal to b.

val (>=) : int -> int -> bool

a >= b tests if the integer a is greater than or equal to b.

val min : int -> int -> int

Takes the minimum of two integers.

val max : int -> int -> int

Takes the maximum of two integers.

Comparison with Stdlib

There are three main differences between Order and the OCaml standard library:

  • The comparison operations implemented in the OCaml standard library are polymorphic, but in Order they are monomorphic (specialized to integers), by default.
  • In the OCaml standard library the base function used in all comparisons, compare, produces integer-based ordering values, while Order uses its own ordering type.
  • Physical equality can be tested with is, and the standard library's (==) operator is deprecated.

The following sections explain in detail the listed differences and the rationale behind them.

Monomorphic Comparison

The reason why polymorphic operations are not included in this library is because they are less efficient than the specialized versions and may cause runtime errors if functions, or other non-comparable values (like definitions in C bindings), are compared.

let hello name =
  Printf.printf "Hello, %s!" name
in
  Pervasives.(hello = hello)
(* Exception: Invalid_argument "compare: functional value". *)

In this example it is clear that a function is being compared, but consider the case where a nested generic data type is being compared which happens to have a function value inside (like a comparator). The comparison will unexpectedly break.

Using monomorphic comparison eliminates the possibility of accidentally comparing functions and encourages the creation of custom comparators for user-defined types.

Ordering Type

The integer-based relative ordering is a historical artifact inherited from the low-level languages like C. As any convention not enforced by the type-system it can lead to errors, like accidentally using the ordering in numerical expressions or forgetting to handle a case. In ML languages ordering can be defined as a union type, providing clear semantics.

Equality Operators

Confusing for new-comers.

Inconsistent with type definition semantics:

type type1 = type2 = A | B
let var1 = var2 = 1