lexicographic order for `AbstractVector` is inconsistent

[matthias314]

According to the documentation for isless,

If isless(x, y) is defined, then so is isless(y, x) and isequal(x, y), and exactly one of those three yields true.

My understanding is that this should hold for all possible arguments. However, on 1.9.0-beta4 and master,

julia> using OffsetArrays
julia> x = [1,2,3]; y = OffsetVector(x, -1);
julia> (isless(x,y), isless(y,x), isequal(x,y))
(false, false, false)

This is because isequal(x,y) gives false if x and y have different index ranges. This is also inconsistent with cmp,

julia> cmp(x,y)
0

since according to the documentation cmp(x,y) == 0 should imply isequal(x,y).

Would it be a solution to define isless(x,y) and cmp(x,y) for AbstractVector only if firstindex(x) == firstindex(y) and to raise an error otherwise? Or would that be breaking?

[oscardssmith]

I believe the more consistent behavior here would be for isless to error when comparing two Arrays a and b where eachindex(a,b)∉(eachindex(a), eachindex(b)) (similarly to how it works with Complex numbers or other collections like Dict that don't have an ordering.

[Seelengrab]

Why is the indexing scheme a factor here in the first place? If the indexing actually should play a role, I'm not surprised that it leads to a partial instead of a total order if the case of comparing and Array and an OffsetArray is not explicitly handled.

[matthias314]

@oscardssmith

eachindex(a,b)∉(eachindex(a), eachindex(b))

What exactly do you mean by that? For my example, eachindex(x,y) gives an error already.

@Seelengrab Are you suggesting to give up the condition that x == y implies axes(x) == axes(y)?

[oscardssmith]

basically the condition where lexicographic order makes sense is if the indices for one of your arrays is a prefix of the indices of your other array.

[matthias314]

@oscardssmith I think that isless is only defined for AbstractVector, not for higher-dimensional arrays (nor for 0-dimensional ones). In that case, isn't your condition the same as firstindex(x) == firstindex(y)?

[oscardssmith]

yeah.

[Seelengrab]

Are you suggesting to give up the condition that x == y implies axes(x) == axes(y)?

Maybe? == is not isequal after all:

julia> ==
== (generic function with 179 methods)

julia> isequal
isequal (generic function with 26 methods)

It's just that the default for isequal falls back to ==, which in turn falls back to ===. I don't actually know what in the isless(x,y), isless(y,x) and isequal trifecta falls back to a default implementation (from what you describe here, it seems to be isequal?), but I still don't follow why the indexing scheme should matter for that at all. If anything, the indexing seems like a third property to track, which is why I said that it's not surprising that it would only result in a partial order. Either the elements are compared lexicographically (for which the relative difference of their indices ought not to matter), or the indices are compared (for which the elements shouldn't really matter). It's not like an OffsetVector and a Vector often describe an "offset prefix" like this:

[-2 -1 0 1 2]
      [0 1 2]

with indices 1:5 and 3:5 respectively, right?

[oscardssmith]

The point is that isless is supposed to always give a total order (or no order at all). Lexographic order isn't defined for arrays with different indices.

[matthias314]

Theoretically we could define isequal(x,y) == true and keep x != y in my example above. To me that would be counter-intuitive, and it would also break OffsetArrays.jl: At present x and y have different hashes, which requires isequal(x,y) to be false. For z = OffsetVector(x, 0) (no offset) one indeed has hash(x) == hash(z).