Re: [Caml-list] Sorting

[jeanmarc.eber@lexifi.com]

En réponse à Xavier Leroy <xavier.leroy@inria.fr>:

> > What are advantages and disadvantages in parametrizing either by '<'
> > or by the 3-way comparison?
> 
> In addition to what has been said already, the 3-way comparison is
> less error-prone with respect to two classic errors:
> 1- passing a "less than or equal" predicate where a "less than"
>    predicate is expected, or conversely;
> 2- passing a predicate that is not a total ordering where a total
>    ordering is expected.
> Both errors could cause the old Sort.array or Sort.list functions to
> misbehave seriously.  These errors are still possible with the 3-way
> comparison approach, but less likely I think.
> 
> - Xavier Leroy

When we are just about "sorting predicates":

I always have a little hesitation about the properties that are
assumed on this functions.

Shouldn't one say clearly in the OCaml doc that these comparison
function are simply suppposed (if I'm not wrong) to be a

  total pre-order, that is a binary predicate that is

  total (of course)
  transitive
  reflexive

BUT NOT necessarly anti-symetric.

Of course, these properties have to be "translated" back into the
3-way comparison approach (thats trivial) but I would find it helpful to
say precisely what properties these functions should have.

Jean-Marc Eber
LexiFi Technologies
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr