Sorting floating-point values, and NaN

[tn]

On Tuesday, 12 November 2013 at 17:59:37 UTC, Vladimir Panteleev 
wrote:
> 1) As above, introduce a "less" function which guarantees 
> transitivity for basic types, and use it in examples throughout.
>
> 2) Improve documentation and visibility of this problem. For 
> example, add this to the documentation of sort:
>
> "The predicate must be transitive (`a<b && b<c` implies `a<c`) 
> in order for `sort` to behave properly - otherwise, the program 
> may fail on certain inputs (but not others) when not compiled 
> in release mode. Note that `a<b` is not transitive for floating 
> points, because the expression will always be `false` when 
> either `a` or `b` is `NaN`."

But 'a<b' is transitive for floating points. The transitivity 
condition (`a<b && b<c` implies `a<c`) says nothing about the 
cases where a and b (or b and c) are incomparable. Transitivity 
is not the problem

> Sort et al don't know how to check "a>=b"... and they can't use 
> "a<b" either, because !(a<b) && !(b<a) implies a==b.

This is the problem, that is, the fact that with '<' you can't 
tell the difference between equal values and incomparable values 
(one or both are NaNs). On the other hand, with '<=' you can. See:

  (a<b) && !(b<a)  -->  a<b
!(a<b) &&  (b<a)  -->  b<a
  (a<b) &&  (b<a)  -->  (not possible)
!(a<b) && !(b<a)  -->  a==b OR incomparable

but

  (a<=b) && !(b<=a)  -->  a<b
!(a<=b) &&  (b<=a)  -->  b<a
  (a<=b) &&  (b<=a)  -->  a==b
!(a<=b) && !(b<=a)  -->  incomparable

Thus, the correct solution would be to modify the functions to 
take "lessOrEqual" as a template parameter instead of "less".

If "less" is kept, then we need another template argument to 
separate equality and incomparability (something like 
"equals(a,b)", or "incomparable(a,b)").