On 11/12/13 1:03 PM, tn wrote:
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));
It is in the other direction, but the latter doesn't compile :o). Again,
it just turns out "a <= b" has the meaning of "a implies b". It's not a
particularly intuitive way to express it.
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).
I agree. Ideas?
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.)
Try it!
Andrei
