On Tuesday, 12 November 2013 at 21:07:48 UTC, Andrei Alexandrescu
wrote:
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?
If you want the isSorted function to always fail if the input
contains NaNs, then I have no other ideas than what I have
already mentioned. It is just not possible by using only "<"
comparison. Something more is needed.
The other way would be to define isSorted to return true if and
only if the _comparable_ elements in the input are sorted (thus
ignoring possible NaNs in between). This is actually
implementable with only "<" comparison, but probably requires
O(n^2) time in the worst case.
