Understanding issorted's lt keyword

[sostock]

@DNF

Where is this made explicit? The closest I could find was

the lt keyword allows providing a custom “less than” function

in the manual, and nothing in the docstring.

That part from the manual is what I meant, and I think it should definitely be added to the docstring.

@DNF

But it does actually accept “lesser than or equal”, since issorted([1,2,2,3]) is true , and that is only sorted if equal is accepted as “less than”.

issorted([1,2,2,3]) uses isless, which is a “lesser than” function, not a “lesser than or equal” function.

[FPGro]

@sostock

issorted([1,2,2,3]) uses isless , which is a “lesser than” function, not a “lesser than or equal” function.

Is that not exactly the source of this confusion? issorted achieves the or equal part because it does not actually assert that the input is sorted, it instead asserts that there are no consecutive elements that are sorted in reverse according to lt, which is also profoundly non-intuitive to me

[DNF]

@sostock

That part from the manual is what I meant

I see nothing about ‘strict total order’ there, only a loose “less than”, which I take to have a conversational, non-formal meaning. “strict total order” is an obscure concept, even for people with maths degrees, I wouldn’t expect most users to have heard of it.

@sostock

issorted([1,2,2,3]) uses isless , which is a “lesser than” function, not a “lesser than or equal” function.

I know it does, but the behaviour is that every element is “less than or equal” to the next.

Is every element in [1,2,2,3] strictly less than the next element? If not, how can one say it is sorted according to a strict total ordering?

[sostock]

Let’s stop talking about the Julia implementation for a second: Every total order relation \leq has an associated strict total order relation < and vice versa. both relations (\leq and <) can be used to describe the same ordering.

@DNF

Is every element in [1,2,2,3] strictly less than the next element? If not, how can one say it is sorted according to a strict total ordering?

The way I see it, it is sorted according to a specified order, which in Julia is supplied via a < relation. In theory, when describing an order, it does not matter whether one uses the non-reflexive (<) relation or the reflexive (\leq) relation to describe that order. But an actual implementation of a sorting algorithm needs to know whether it is working with a < or a \leq relation, otherwise it might produce garbage.

It was decided that the Julia sorting machinery uses the < relation for describing an order, not the \leq relation. I don’t know why this was chosen. Maybe it was easier to implement the sorting algorithms that way, maybe it’s just because there is an isless function but no islessorequal function.

I can see that this decision to use < instead of \leq to describe orders seems wrong if you assume that

@DNF

issorted([a, b]; lt=foo)  <==> foo(a, b)

should hold.

[DNF]

So the thing is that this is an extremely subtle point, unless you have a degree in this specific area. For a very ‘ordinary’, common, functionality that probably most users think they grasp intuitively, the documentation would need a very dramatic beefing up.

I mean, is it reasonable to expect that people should be well-versed in set theory to be able to use a normal sort function?

[Sukera]

Some sorting algorithms are sensitive to whether \le or \lt is used, because they may depend on the initial order the to-be-sorted elements (that are =) appear in. Sorting algorithms that preserve that order between equal elements are called stable (there may be some other distinguishing feature the sorting implementation in question isn’t aware of). It may be that if \le were the default, we’d have a harder time implementing these (or they wouldn’t be as efficient as possible?).

Sorting and knowing what order to sort by is not necessarily a trivial task.

[Jean_Michel]

Excuse me, I am jumping in the conversation after 46 posts, but I see immediately what is wrong.
The Julia manual just uses the mathematical definition for what is a total order. A total order is given
by a function < such that

• for any a,b we have either a<b or b<a or a==b (but only one of them)
• if a<b and b<c then a<c

In other words, a total order is what in this conversation you call “strict total order”.
The operator <= does not satisfy the axioms of a total order so should not be used with sort or issorted.

[DNF]

@Jean_Michel

The operator <= does not satisfy the axioms of a total order so should not be used with sort or issorted .

But then it becomes impossible to sort non-unique vectors, since they cannot obey a total ordering, so it doesn’t seem very useful.

Also, the docs don’t say you cannot use certain orderings, and the sort function does not reject <=.

I still don’t get what’s the big deal about ‘strict total order’. Why can’t you sort data in a loose, partial, laissez-faire, off-the-cuff order?

[Jean_Michel]

@DNF

But then it becomes impossible to sort non-unique vectors, since they cannot obey a total ordering, so it doesn’t seem very useful.

Not at all. When sorting a non-unique vector the equal elements will become consecutive. The algorithm in Julia for sort uses the definition I gave for sort and sorts perfectly well non-unique vectors
and the result is issorted. The Julia devs used the mathematical definition for a total order to be able
to follow books on sorting which use the same definition (read for example Knuth).

[DNF]

But how can it be sorted if each element isn’t < than the next? Each element is, however, <= than the next, so <= is the correct ordering.

What am I missing? This is really frustrating.

[Jean_Michel]

Given a total order <, you can define a “less than or equal” relation <= which is:

• a<=b if a<b or a=b

But this relation is not a total order. A sequence a_1,…,a_n is sorted if a_i<a_{i+1} or a_i=a_{i+1}, or
in other terms a_i<=a_{i+1}. The function you give to sort must be a total order, otherwise it will give
unpredictable results, so even though a function < can be used to define a function <=, you should not give <= as argument to sort (or issorted) otherwise it will misbehave.

[DNF]

I still don’t understand. I’ll quote my recent question:

@DNF

But how can it be sorted if each element isn’t < than the next? Each element is, however, <= than the next, so <= is the correct ordering.

[gustaphe]

The way I see it, should-wise: issorted should simply check whether lt holds for each consecutive pair. sort should have an output for which issorted is true, if possible. The default lt should be <=. sort([1, 1, 2]; lt=isless) should error out, because it can’t be done, just like sort([1, im]; lt=isless) can’t be done.

Implementation wise, the possibility of using arbitrary comparisons means it can’t be entirely specialized on type (like above), and it’s not even guaranteed there is an algorithm, consider lt=(x, y)->false. But the domain of lt for sort is a strict subset of that for issorted.

[Jeff_Emanuel]

The point of issorted is to check whether calling sort is useful or necessary. Think of it as asking “If I call sort with this value for its lt parameter, will it return the array unchanged?” You shouldn’t expect any more or less of it.

[goretkin]

@gustaphe

The way I see it, should -wise: issorted should simply check whether lt holds for each consecutive pair.

That means that the default lt = isless would be wrong, since it would give issorted([1, 1]) == false.

You could then suggest the default be lt = <=, but note that the fallback for <= is defined in terms of <:

JuliaLang/julia/blob/d6c092d6d73be9b41b5b8fef30d882fdb63a8d20/base/operators.jl#L401

And < is defined in terms of isless:

JuliaLang/julia/blob/d6c092d6d73be9b41b5b8fef30d882fdb63a8d20/base/operators.jl#L352

If you simply define isless and == (EDIT: not isequal), you get the desired (probably) definitions of the other operators. I’d say that this is nothing more than a design choice, but it’s one that works pretty well in my opinion. And indeed you can write issorted in terms of isless: instead of checking that every consecutive element satisfies a property, you instead check that no consecutive element violates a property.

I understand that this extra negation and swapping of the arguments is not the first definition of issorted that some people are thinking of. But the definition that is in Base is self-consistent. That’s not to say that this can’t be better documented.

I’ll add that there might be cases where it’s better to define isless on your type (possible a wrapper type) than it is to pass in a function for lt. I asked about these two choices once upon a time: Designing APIs. defining new methods versus passing in functions

@goretkin

Once you define isless on your type (your thing), then you can use min , minimum , sort , you can use the lexicographic ordering induced by isless on NTuple{Thing} , and so forth. (So, here’s a benefit of the second API)

[DNF]

@goretkin

instead of checking that every consecutive element satisfies a property, you instead check that no consecutive element violates a property.

Actually, it seems that the current implementation checks whether the reverse order does not satisfy the property, and those are not equivalent, thus causing all this confusion.

@Jeff_Emanuel

The point of issorted is to check whether calling sort is useful or necessary.

That seems backwards to me. The fundamental concept is being sorted, while sorting is just any algorithm that causes a sequence to be sorted. This definition is at least much easier to explain. I get a bit of a headache trying to grasp the ‘inverse’ definition of the concepts, that you are advocating.

[goretkin]

@DNF

Actually, it seems that the current implementation checks whether the reverse order does not satisfy the property, and those are not equivalent, thus causing all this confusion.

I might have been unclear. To emphasize, I said “a property”, and you’re talking about “the property”. Once someone understand that the property is not lt(this_element, next_element), but instead !lt(next_element, this_element), I don’t see what confusion remains.

And I’ll argue that you don’t need to look at the implementation to know that that’s what’s happening, if you understand that the default value of lt is isless, and that issorted accepts any function for lt.

[DNF]

And I do understand that this is the case. It just seems completely bizarre.

Why is it done like this? Why not then supply a “greater than” comparison?

I realize this won’t change, and is probably ‘correct’. It’s just so mind-bendingly, brain-explodingly counterintuitive. I wish I could ‘get it’.

[goretkin]

@DNF

I get a bit of a headache trying to grasp the ‘inverse’ definition of the concepts, that you are advocating.

Note that I am justifying the definition of issorted by discussing the function isless. Julia (Base and software ecosystem) is unlike any other in my experience in how well it does generic programming. By design, isless and isequal is more “fundamental” than the <= that you are advocating for.

We are lucky when outcomes of careful design for generic programming aligns with the expectations of every user, and we appear not to be lucky this time. It is obvious to me that the solution is better documentation, instead of re-working how comparisons are done in Julia.

[DNF]

@goretkin

By design, isless and isequal is more “fundamental” than the <= that you are advocating for.

But what’s the relevance of that? The question I’m struggling with is “what does it mean for a sequence to be sorted according to some comparison operator?”

This switching of order and negation causes weird results, and the motivation is opaque to me.