opCmp, [partial/total/pre]orders, custom floating point types etc.

[John Colvin via Digitalmars-d]

Background:
Some important properties for binary relations on sets that are 
somewhat similar to the normal ≤/≥ on the real numbers or 
integers are:

a ≤ a (reflexivity);
if a ≤ b and b ≤ a, then a = b (antisymmetry);
if a ≤ b and b ≤ c, then a ≤ c (transitivity);
a ≤ b or b ≤ a (totality, implies reflexivity);

Definitions:
A preorder obeys reflexivity and transitivity.
A partial order obeys reflexivity, transitivity and antisymmetry.
A total order obeys transitivity, antisymmetry and totality.
A total preorder obeys transitivity and totality but not 
antisymmetry

Examples:
Arrays ordered by length, vectors ordered by euclidian length, 
complex numbers ordered by absolute value etc. are all total 
preorders.
Integers with ≤ or ≥ form a total order.
float/double/real obey antisymmetry and transitivity but not 
reflexivity or totality.

Implementations in D:
Total order: opCmp with "consistent" opEquals to enforce 
antisymmetry.

Total preorder: opCmp with "inconsistent" opEquals to break 
antisymmetry.

Preorder or partial order: not possible in D, opCmp insists on 
totality.

Antisymmetry and transitivity but not reflexivity or totality, 
e.g. custom float: not possible in D, opCmp insists on totality 
(no way for opCmp to signify nan comparisons, either with nan 
(reflexivity) or others (totality & reflexivity)).


Solutions to the above problems:

1) opCmp - or some extended, renamed version of it - needs 4 
return values: greater, lesser, equal and 
neither/unequal/incomparible. This would be the value that is 
returned when e.g. either side is nan.

or, less intrusively and more (runtime) efficiently:

2) Introduce a new special function `bool opCmpOrdered(T rhs)` 
that, if defined, is used to shortcircuit a comparison. Any 
previous lowering to `a.opCmp(b) [<>]=? 0` (as in 
https://dlang.org/spec/operatoroverloading.html#compare) would 
now lower to `a.opCmpOrdered(b) && a.opCmp(b) [<>]=? 0`. E.g. `a 
 >= b` becomes `a.opCmpOrdered(b) && a.opCmp(b) >= 0`. If 
opCmpOrdered isn't defined the lowering is unchanged from before 
(or opCmpOrdered defaults to true, same thing...).

Bigger example: a custom float type

struct MyFloat
{
     // ...
     bool isNaN() { /* ... */ }
     bool opCmpOrdered(MyFloat rhs)
     {
         if (this.isNaN || rhs.isNaN) return false;
         else return true;
     }
     int opCmp(MyFloat rhs)
     { //can assume neither are nan
         /* ...  */
     }
     bool opEquals(MyFloat rhs)
     {
         if (this.isNaN || rhs.isNaN) return false;
         else /* ... */
     }
}

unittest
{
     MyFloat a, b; // has .init as nan, of course :)

     static allFail(MyFloat a, MyFloat b)
     {
         // all of these should short-circuit because
         // opCmpOrdered will return false
         assert(!(a==b));
         assert(!(a<b));
         assert(!(a<=b));
         assert(!(a>b));
         assert(!(a>=b));
     }

     allFail(a, b);
     a = 3;
     allFail(a, b);

     b = 4;
     assert(a!=b);
     assert(a<b);
     assert(a<=b);
     assert(!(a>b));
     assert(!(a>=b));

     a = 4;
     assert(a==b);
     assert(!(a<b));
     assert(a<=b);
     assert(!(a>b));
     assert(a>=b);
}


P.S. This is not just about floats! It is also very useful for 
making types that represent missing data (e.g. encapsulating 
using int.min for a missing value). I can only come up with 
strained examples for preorders and partial orders that I would 
want people using < and > for, so I won't speak of them here.

P.P.S. Note that I am *not* trying to extend D's operator 
overloading to make > and < usable for arbitrary binary 
relations, like in C++. This small change is strictly within the 
realm of what <, > and = are already used for (in D, with 
floats). I'm convinced that if you wouldn't read it out loud as 
something like "less/fewer/smaller than" or "greater/more/bigger 
than", you shouldn't be using < or >, you should name a separate 
function; I don't think this proposal encourages violating that 
principle.