Julia: Usage of `isless`

[sebasguts]

Dear all,

I think there is a mismatch between the documentation and implementation of isless. I am not sure which one should be correct. The documentation states

  isless(x, y)

  Test whether x is less than y, according to a canonical total order. Values that are normally unordered, such as NaN, are ordered in an arbitrary but consistent fashion. missing values are ordered last.

  This is the default comparison used by sort.

This suggests that any two objects are always comparable, and the result is consistent. However, most comparisons fail with a method error, e.g.,

julia> isless(1,[2,3])
ERROR: MethodError: no method matching isless(::Int64, ::Array{Int64,1})    

What is the intended behaviour of isless. If the intended behaviour of isless is to only compare objects of the same "typeclass", I would say the documentation is misleading. For reference, my current Julia version is 1.1.0 release:

   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.1.0 (2019-01-21)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/  

[eulerkochy]

I guess that there is no problem in the documentation. total order demands that x and y belong to the same set X and then their relations are compared. See this So, isless(1, [2, 3])) is syntactically wrong, imo.

[cormullion]

what is a "canonical total order"? First Google hit is the Julia docs... :)

[eulerkochy]

imo canonical here refers to a synonym of the word general Here :wink:

[cormullion]

"general total order" sounds like it should mean something to me, but ... 🤔

[eulerkochy]

umm, it's like putting a fancy name for total order and as far as my discrete maths knowledge extends, i haven't encountered a term called general total order :baby:

[elextr]

I would suggest (putting words in the documentation writers mouth) that canonical is used in this context to mean a natural or definitive property of the objects that leads to an ordering.

Objects that are not naturally ordered like 1 (a number) and [2,3] (a list) do not have such a property.

[sebasguts]

Thank you for your comments. Unfortunately, this does not really solve my problem.

I guess that there is no problem in the documentation. total order demands that x and y belong to the same set X and then their relations are compared.

Exactly. However, there is no set specified, so I assumed it is the set of all Julia objects. One might argue that the total order is just given on certain subsets, but I guess those should be specified then (they are in fact specified by the implementation, but not by the documentation).

So, isless(1, [2, 3])) is syntactically wrong, imo.

I think it is syntactically right, the question is more about the semantics of the isless function, which I am trying to find out in this issue.

I would suggest (putting words in the documentation writers mouth) that canonical is used in this context to mean a natural or definitive property of the objects that leads to an ordering.

I have read the canonical as something that is arbitrary, but fixed, in a sense that it does not depend on the Julia session.

Let me give you some insights why I am interested in this (and particularly interested in isless providing a global (as in all objects) total ordering):
I am currently working on an interface from the CAS GAP to Julia, and GAP likes to have a global total order on all on it's objects, because it relies on that sorting in quite some situations, like producing sets and so on. One could argue that this should be better done via hashes, but having a global ordering here also has advantages.

[eulerkochy]

One could argue that this should be better done via hashes, but having a global ordering here also has advantages

imo, one way out would be to overload isless with an extra parameter of Ordering which could solve the problem.

[sebasguts]

imo, one way out would be to overload isless with an extra parameter of Ordering which could solve the problem.

I do not really see how this is a solution tbh. What should this parameter do?

[elextr]

For reference from the GAP manual:

Only for the following kinds of objects, an ordering via < of objects in different families (see 13.1) is 
supported. Rationals (see IsRat (17.2-1)) are smallest, next are cyclotomics (see IsCyclotomic (18.1-3)), 
followed by finite field elements (see IsFFE (59.1-1)); finite field elements in different characteristics are 
compared via their characteristics, next are permutations (see IsPerm (42.1-1)), followed by the boolean 
values true, false, and fail (see IsBool (20.1-1)), characters (such as {}a{'}', see IsChar (27.1-1)), and lists 
(see IsList (21.1-1)) are largest; note that two lists can be compared with < if and only if their elements
 are again objects that can be compared with <.

Julia objects do not have this relationship naturally, IIUC you would have to code it yourself.

[fingolfin]

Note that GAP is itself trying to get away from this reliance on a "total order of all objects", and in fact higher level GAP objects (e.g. groups), or newer low-level objects (like floats) do not adhere to this.

[fingolfin]

I read "... according to a canonical total order " as saying: "if the comparison succeeds, then it should adhere to some (unspecified) total order." The question is: what is that information supposed to tell the reader? My guess is that it wants to convey the information that the order implement by isless should be transitive and satisfy trichotomy, in the following sense:

• transitive: if isless(x,y) and isless(y,z) succeed and return true, then also isless(x,z) should succeed and return true;
• trichotomy: if isless(x,y) succeeds, then also isless(y,x) and isequal(x,y) should succeed, and exactly one of them should return true

If that's indeed what is intended, then I'd say it would be better to say so explicitly. If this is not what is intended (or maybe not all of it), then I'd still say it should be clarified, with even strong conviction ;-)

[JeffBezanson]

Yes, those properties are what the documentation is talking about. It says "total order" to clarify that it's not a partial order, unlike e.g. < on floating point numbers.

It can be interpreted as "if isless(x,y) returns a value, then that value reflects the ordering of x and y in some total order". But it's supposed to be understood that functions only work on arguments for which method definitions exist. Only a small handful of functions like === actually work on every value. I believe it is unusual to provide a total order on all objects; we assumed most people would not expect that to exist.

[StefanKarpinski]

Could certainly use clarification in the docs if someone wants to take a crack at it.

[sebasguts]

Thank you all very much for your feedback, I think that clarifies it pretty much.

It would be really cool if the doc's could be clarified, I will try to provide a PR, trying to wrap up @JeffBezanson s description as short and unambigiously as possible.