On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei Alexandrescu
wrote:
Consider we define equiv(a, b) as (a, b) => !less(a, b) &&
!less(b, a).
If at least one of the numbers is NaN, all comparisons return
false. That puts NaN in the same equivalence class with all
numbers, including numbers that are deemed in distinct
equivalence classes. That's where NaNs mess things up, and
that's what we need to assert. Consider three numbers a, b, and
c. Then the following must pass:
assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));
("<=" on Booleans is actually implication.)
Shouldn't the implication be to the other direction? Then it
becomes
assert((equiv(a, b) && equiv(b, c)) => equiv(a, c));
That test will fail with NaNs and should be part of isSorted,
sort etc.
But it requires that the input contains at least three elements.
And it has to test a lot of possible triples (a,b,c), which I
think requires at least O(n^2) time. And it does not fail
consistently whenever the input contains at least one NaN
(consider an input that contains only NaNs).
We should also check such as:
assert(!less(a, a));
assert(less(a, b) <= !less(b, a));
These should be checked in sort only; isSorted does not need
these.
The latter fails also if a==b. (Unless the direction of the
implication is again wrong.)
