Is there a definitive expanation or definition of those terms with respect to Julia?
I thougth I had a clear understanding, but am a little bit unsettled after I saw cmp(::AbstractArray, ::AbstractArray) and the documentation of cmp(::AbstractString, ::AbstractString).
See #25401 and #25407.
The string case is just a simple mistake in the doc string.
Until yesterday, arrays never supported isless. I blindly renamed lexless for arrays to isless, problem being it does not look at the shape. I think some good options are (1) restrict it to vectors, or (2) end the function by calling cmp(size(A), size(B)) instead of cmp(length(A), length(B)).
Another option would be to do lexicographical ordering on elements in linear ordering (so column major for dense arrays) but error if size(A) != size(B).
I think, we should stick to the existing documentation and define isless, cmp only, if the arguments have the same type and the type has a natural, general, agreed, and commonly expected (canonical) total order.
That is IMO not the case for any AbstractArray, also not for Vector, even if they have the same shape.
For vectors, I could imagine a kind of lexical ordering similar to AbstractString. That would be a total order, but is not canonical. Who would sort cartesian coordinate vectors lexicographically?
Calling cmp(size(A), size(B)) would end in a discussion about comparison of tuples.
Stefan’s option would be the best approach, but not resolve my objections.
The issue with that is that we ended up having these lexless and lexcmp functions hanging around even though we don’t have any behavior defined for arrays for isless or cmp anyway. It just seems pointless not to define isless and cmp for arrays in the only way we provide to order them.
That is not an argument. If we define isless in a certain way we suggest to the user, that it is “The canonical total order” of the type. That is not the case for vectors and lexicographic. Rather it would be better to keep islexless and lexcmp to indicate to the user, that he is not using a canonical order.
With the same argument we could define isless and cmp for sets, because it is easy to construct a lexical order for sets of (totally) ordered element types, but the canonical order for sets is and remains the partial order implied by set-inclusion.
In the sort functions it is possible to use any user-provided ordering by the lt argument. Would it make sense to extend this use to max and all other functions, which rely on isless to be defined?
It would also be possible to attach user-defined comparison behaviour to user defined types. And - one of my favorite ideas - make user defined subtypes of arrays possible? Yes - I think about inheritance from concrete types, which adds no state, but allows methods to dispatch on the subtype.
I can see the argument that it is more useful to define a default isless function than to leave it undefined, even if the choice of ordering is ambiguous. That way things like sort will at least give some reasonable ordering, and the user can always specify a different ordering manually.
But by the same argument, shouldn’t we also define an isless(::Complex, ::Complex) method via lexicographical ordering? (It will have the essentially same algebraic drawbacks as lexicographical ordering of arrays. Not quite, because arrays don’t define *, see below.)
We still shouldn’t define < for arrays or complex numbers, of course: I would say that < should be reserved for cases where there is an unambiguous standard ordering (not including NaN).
Sure, that seems reasonable to me. I wonder if polar ordering for complex numbers isn’t the more commonly useful one though. Isn’t that how complex eigenvalues are usually sorted? OTOH, I guess that lexicographical ordering has the advantage of being simpler and more obvious. As long as we provide polar ordering functions, it’s easy enough to ask for.
sortrows sorts lexicographically, so there’s at least some precedent for comparing arrays lexicographically by default.
About that… < has a fallback that calls isless; maybe we should remove it?
Defining a default ordering for complex numbers sort of rubs me the wrong way. I think because they’re so similar to objects that have an ordering, and yet they don’t.
The purpose of this thread was to settle a solid fundament on how we treat ordering in Julia. In the moment it looks like we are throwing everything away, we had already as a consensus:
isless defined <=> there is a canonical order inherent in the type
That is not the case for complex or vectors or arrays.
Sorting is not a justification to define isless, because there is this lt named argument for non-standard wishes.
We have also long had an isless method for tuples that uses lexicographical ordering…
Tuples are different because they don’t support +.
The problem with defining < for arrays or complex numbers is that there is no way to do it that this consistent with addition (that is, you want a < b to imply a+c < b+c for all c and a, but this is impossible). Correction: You can’t do it consistent with addition and multiplication: you also want 0 < a to imply 0 < a*a. For arrays, there is no * operation, and lexicographical ordering is okay with + alone.
I think, that is a good example to explain how I understand “canonical”. Order relations are mathematical objects, which and they interrelate with other mathematical objects, like additive structures. There is a theory behind that, which works like a mobile in equilibrium - if you change one little part, it gets in motion and a lot of things do not work any more. That is why I am reluctant to extend the domain of certain functions, which handle mathematical objects to types, which do not behave “mathematically”.
Let me come back to the original subject: how and if should isless and cmp be defined for AbstractArray?
I would recommend, to keep the following contract valid:
For each a and b of the same type, which is in the domain of isless/cmp (ìsless(::T,::T) where T) exactly one of the following statements shall be true
Either isless(a,b) === true or isless(b,a) === true or isequal(a, b) === true.
Also cmp(a,b) < 0 <=> isless(a,b) and cmp(a,b) > 0 <=> isless(b,a) and cmp(a,b) == 0 <=> isequal(a,b).
Besides that, of course associatitvity, antisymmetry, reflectivity has to be respected.
This contract can be followed by a lexicographical order for arrays, if you make the following restrictions:
It is an open decision, if we restrict that to one-dimensional arrays (only one of the size(a) elements is different form 1).
For Tuple, the decision to use lexicographical ordering has been made long ago and is ok. Tuples are in my reception less “mathematical” than arrays and vectors and serve different purposes.
For complex numbers, ordering would be surprising and on purpose. If there is a reason to present or process a set of complex numbers in a certain order, there are probably as many different orders as there are application uses. For example I once sorted eigenvalues first by abs of the real part, then by the negative of the imaginary part - and that was appropriate for my use case.
I would prefer to not provide a standard ordering, but delegate that to the user. Reason
For most types, they are the same, and you’d have to define two comparison methods, which would be annoying. Maybe just define a < method for arrays that throws a method error?
Just to be clear, lexicographical ordering has exactly the same problem for complex numbers and arrays in relation to +, due to the isomorphism between complex numbers and two-element arrays. That’s why it doesn’t make sense to me to define a lexicographical isless for one and not the other.
. In a<b ⟹ a+c<b+c; the problem for complex numbers comes in the other requirement for an ordered field: you also want 0<a to imply 0<a*a, which is violated for lexicographical comparison with a=im. Arrays don’t have this problem because they don’t define *.isless for arrays and not for complex numbers. But it is still true that isless already has fewer “algebraic” requirements than < in Julia…On the other hand, since we have separate (non-synonymous) functions isless and <, only < seems like the “algebraic” one to me. isless, in contrast, is used purely for sorting and searching, and so I don’t think it needs to satisfy the algebraic properties that < does.
(For example, isless and isequal already violate isless(a,b) ⟹ isless(a+c,b+c) for floating-point numbers. e.g. try a=1, b=2, c=NaN. < makes NaNs unordered, so it is in a different boat here. The use of the term “partial order” is still a bit funny for < because a strict partial order would probably throw an error for NaN < NaN.)
Defining <(x::T,y:T) where T = isless(x,y) is a good idea, in general, because if for a type T a canonical total order is defined, it is natural to use that also for <.
In the other case, the contract for < is less restrictive than for isless in that it allows to implement partial orders. In the case of arrays (of same shape) that would be typically element-wise comparison. So
<(a::AbstractArray{T},b::AbstractArray{T}) where T =
begin size(a) != size(b) && error...; all(isless.(a, b)) end
would be useful. Kind regards.
Element-wise comparison is not a partial order. It isn’t an order at all. (It’s not a binary relation.)
Besides, we already have .< and isless. for element-wise comparison of arrays.
Maybe you meant <(a,b) = all(isless.(a,b))? I don’t think this would be terribly useful.
For me, < also has an “algebraic” co-notation, because it is so frequently used for real numbers. Unfortunately the completion of ℝ with NaN is not a field any more. Arguments which use NaN are not mathematical. At the other hand Float64 is also not exactly a field, and the mathematical branch of numerics has been handling the difference. The discussion about the differences between < and isless should be separated for the areas of Real (which does not contain Complex nor arrays) and other types.
For Real floats, the pair if isless/isequal models an absolute order including the special values NaN and -0.0, which is not the case for </==.
The pair of </== are better suited for arithmetic operation, and they handle -0.0 and NaN differently.
For other types, it has been defined to use isless/isequal for total orders and == to fall back to isequal. The < has a priory no meaning for those types. For convenience it has been defined to fall back to isless.
For example for Set there is in general no useful total order, and isless is not defined. The natural order of sets is implemented by issubset.
My argument against giving a total order to Complex was because there no mathematically founded definition for such an order available (no mathematical theory about orders on complex numbers), and every order we define is as arbitrary and on purpose as the other.
…