The polymorphic compare function can be used to instantiate OCaml predefined functors (Map.Make, Set.Make, ...). In this case we only need to know that it behaves like an order but it could be useful to understand how it is actually defined. For example, how to be sure that the following function correctly computes the max of a list :
let rec max_list = function
| [] -> None
| h::t -> max (Some h) (max_list t)
I first thought that constructors defined earlier are smaller than the ones defined later. However it does not seem to be the case as
max Non (Som 2)
has value Som 2 : opt
whether opt is defined as
type 'a opt = Non | Some of 'a
or as
type 'a opt = Some of 'a | Non.
To compare values of an algebraic-datatype, I expect it to compare the constructors and then, if those are the same, compare their arguments. Why is it not true, and how is comparison defined?
If you look at the language definition for the compare function and the preceding comparison operators (currently at https://caml.inria.fr/pub/docs/manual-ocaml-4.08/core.html#sec551) you'll see that there's no explicit guarantee of the order of the different constructors of a variant type. It's only guaranteed that it represents a total order.
If you want a specific order, you need to define your own comparision function.
In the current implementation, the constructors with no arguments (nullary constructors) are treated as less than the constructors with arguments, even if they appear later in the definition. In my opinion, it wouldn't be wise to depend on this, since there's no explicit guarantee in the language definition.
# type ab = B of int | A;;
type ab = B of int | A
# A < B 2;;
- : bool = true
# type cd = C | D of int;;
type cd = C | D of int
# C < D 2;;
- : bool = true
# type ef = E | F;;
type ef = E | F
# E < F;;
- : bool = true