What should `issorted` return when an order isn't defined for the elements, but a comparison works?

General Usage
1

Currently, issorted returns true by default, even if the elements do not have a defined order. For example,

julia> issorted([NaN, NaN])
true

In this case, because NaN is a floating-point number, the comparison works, except we obtain

julia> NaN >= NaN || NaN < NaN
false

This reflects the fact that NaNs are unordered. Having issorted return true in this case doesn’t seem ideal. I wonder if there might be a better way to convey the message here?

2

It appears

julia> isequal(NaN, NaN)
true

The docstring states

Furthermore, isequal is linked with isless, and they work together to define a fixed total ordering, where exactly one of isequal(x, y), isless(x, y), or isless(y, x) must be true (and the other two false).

I suppose this is what sorting uses.

3

This is now better documented on master, see the new sort! documentation.

In short, the sort functions don’t use isequal, by default they use the ordering defined by isless. Values a and b are considered “equivalent” (a generalization of “equal”) if isless(a,b) and isless(b,a) both return false. This is the case for a=NaN, b=NaN so you get issorted([NaN, NaN]) == true.

2 Likes
4

FIXED: sort! to sort thanks to mikmoore.

A good spec for issorted operation is to satisfy:

sort(V) == V → issorted(V) == true

if the stronger spec:

sort(V) == V ↔ issorted(V) == true

is adopted, then issorted([NaN]) should be false.

But, as usual, NaN logic is tricky as hell, and perhaps erroring will do the developer a favor in pointing to a necessary fix before NaNs eat up the whole calculation.

5

A container is (by default) considered sorted if isless(x[i+1],x[i]) == false for all valid i. Since isless(NaN,NaN) == false, it holds that issorted([NaN,NaN]) == true. More generally, any array of real floats is sorted if the non-NaN elements are sorted (including -0.0 coming before +0.0) and any NaNs are at the very end. Note that any non-NaN is isless than NaN – e.g., isless(Inf,NaN) == true.

If you want check that an array is strictly increasing, try something like all(i -> x[i] < x[i+1], eachindex(x)[begin:end-1]).

2 Likes