Does work compare for all types?

Question

Consider type t and two variables x,y type t .

Will the call compare xy valid for any type t ? I could not find a counterexample.

Answer 1

The polymorphic comparison function works by recursively examining the structure of values, providing ad-hoc a complete ordering of OCaml values ​​used to determine the structural equality verified by the polymorphic operator.

This, by definition, is not defined for functions and closures, as @antron noted. The recursive nature of the definition means that structural equality is not defined for values ​​containing a function or closure. This recursive nature also implies that the comparison function is not defined for recursive values, as @antron is also mentioned.

Structural equality and, therefore, the comparison function and comparison operators are not aware of structural invariants and cannot be used to compare (softly) advanced data structures such as Sets, Maps, HashTbls, etc. If you want to compare these structures, you need to write a specialized function, so Set and Map define such a function.

When defining your own structures, a good rule is to distinguish

• specific types that are defined only in terms of primitive types and other specific types. Concrete types should not be used for structures whose processing expects some invariants, since it is easy to create arbitrary values ​​of this type that violate these invariants. The functions and functions of polymorphic comparison are suitable for these types.

• abstract types whose concrete definition is hidden. For these types, it is best to provide a specialized comparison function. The mixin library defines a mixin comparison , which can be used to derive comparison operators from the implementation of a specialized comparison function. Its use is illustrated in README .

Answer 2

It does not work for function types:

 # compare (fun x -> x) (fun x -> x);; Exception: Invalid_argument "equal: functional value". 

Similarly, it will not (usually) work for other types whose values ​​may contain functions:

 # type t = A | B of (int -> int);; type t = A | B of (int -> int) # compare AA;; - : int = 0 # compare (B (fun x -> x)) A;; - : int = 1 # compare (B (fun x -> x)) (B (fun x -> x));; Exception: Invalid_argument "equal: functional value". 

It also does not work (usually) for recursive values:

 # type t = {self : t};; type t = { self : t; } # let rec v = {self = v};; val v : t = {self = <cycle>} # let rec v' = {self = v'};; val v' : t = {self = <cycle>} # compare vv;; - : int = 0 # compare v v';; (* Does not terminate. *) 

These cases are also listed in the documentation for compare in Pervasives .