# 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``````