Understanding issorted's lt keyword

[jzr]

@goretkin

So the footgun, aside from the indirect documentation and lack of explicit counter examples is that <= seems like a reasonable choice for a “less than” function to you.

Yeah, basically.

In other words, the issue is that it’s asking for a function that has certain properties when that isn’t what I expect it to be asking for, and it gives undesirable results when I give it something that I naively think is similar.

Putting a warning message on it may help sometimes, but designing the API so that it doesn’t need a warning message since it already conforms to expectations may be more successful.

[goretkin]

@jzr

Putting a warning message on it may help sometimes, but designing the API so that it doesn’t need a warning message since it already conforms to expectations may be more successful.

I think it’s obvious that it is not possible to design an API that conforms to everyone’s expectations, though it is a worthy ideal to keep in mind. But there are other important ideals, such as consistency, and enabling generic programming. Julia Base has broken the “tie” between “define <= in terms of < or vice versa?”. The definition of issorted follows as a consequence, consistently.

You do not appear to be considering all of the other implications of changing the chosen design. Since you are not the OP, it also seems that you have not run into this problem yourself.

If you haven’t already, please read PSA: Julia is not at that stage of development anymore .

[jzr]

@goretkin

You do not appear to be considering all of the other implications of changing the chosen design.

I guess that’s true.

@goretkin

Julia Base has broken the “tie” between “define <= in terms of < or vice versa?”. The definition of issorted follows as a consequence, consistently.

Could you spell out why this follows?

[FPGro]

I’ve just dug out all the history of the issorted function (which is surprisingly hard) and came to the conclusion that it’s fine. What transpired is, that at no point in this whole thing, using <= as an ordering inducing function was considered to be meaningful.

When the (precursor) of the current implementation lt(this, prev) (not literally) was introduced, sorting orders were actually determined by a pair of lt, le functions, but the second part was dropped, probably because it is somewhat redundant when one sticks to the requirements of “less than” for inducing order. It’s clear that there is no “less equallier” function belonging to <= like <= belongs to <.

Fast forward: how order is defined is actually documented by isless, much more clearly than what sort has to say about the lt keyword. The critical part is that the lt keyword gets tranformed to a Base.Lt, which is actually pretty clear about what you can meaningfully do with it:

help?> Base.Lt
  Lt(lt)

  Ordering which calls lt(a, b) to compare elements. lt should obey the same rules as implementations of isless.

So we should probably just make issorted and sort point to Base.Lt (or isless directly) for the explanation of the lt keyword and consider it done.

The fact that using lt = <= actually yields an equivalent of issorted && allunique is a peculiar implementation detail but not more then. (Answering the initial question) Exploiting this is probably still relying on an implementation detail but one that is unlikely to change anytime soon.

[gustaphe]

To get the desired behaviour:

using IterTools.partition
isinorder(x; order=<=) = all(t->order(t...), partition(x, 2, 1))

isinorder([1, 1, 2]) == true
isinorder([2, 1, 1]) == false
isinorder([1, 1, 2]; order=<) == false
isinorder ([1, 1, 2]; order=x->true) == true

[goretkin]

This is in essence what I wrote 80 posts ago: Understanding issorted's lt keyword - #7 by goretkin

[DNF]

I’m fine with this being better documented, and not changed.

But I must say I am a bit baffled that it’s apparently so hard to see why the current behaviour is surprising. Understanding the current behaviour requires an extremely high level of mathematical sophistication. If you are capable of that then it makes sense (I presume, I’m only a Msc in mathematics, I don’t think this is within my intellectual reach), and I don’t mind that Julia normally chooses ‘correctness’ over intuition.

But after this many posts, it’s really strange that there is apparently zero understanding among some, such as @goretkin, that this

jl> issorted([1,2,2,3]; lt=<=)
false

jl> issorted([1,2,2,3]; lt=<)
true

is surprising and weird for people below the PhD level. It may be correct, but it is strange.

What all of this has to do with which is more ‘fundamental’ of isless or < is, unfortunately, also beyond me. It’s fine that isless is the default, because it’s more fundamental, but that alone doesn’t explain why <= cannot also be used.

[sostock]

@mkitti

What I’m not sure about is if I would be I’m exploiting documented behavior or an implementation detail by using issorted( ..., lt = <=) .

I would say it is an implementation detail that issorted(A, lt=<=) behaves as issorted(A) && allunique(A). It is definitely not documented behavior. It also doesn’t work if NaNs are involved:

julia> issorted([2, NaN, 1], lt=<=)
true

(NaN is not ordered with < and <=, which means that x < NaN, x <= NaN, NaN < x and NaN <= x return false for every x. That’s why lt=isless is the default, not lt=<.)

You can certainly use it (if you know that you don’t have to deal with NaN or have to distinguish between -0.0 and 0.0), but it might be more clear to write your own function for this. You could just copy the implementation of issorted and adapt it to your case.

[sostock]

What about adding something like the following to the sort! docstring:

If a custom lt function is supplied, it should behave like a “less than” function (as opposed to a “less than or equal” function), i.e., for every x and y, only one of lt(x,y) and lt(y,x) can return true.