Too severe precondition for slice::sort_by?

help
21

I don't think words phrases like 'funny sounding' and 'fake-comparison' add anything to a technical discussion. So let's concentrate on the content.

Using < or a cmp with an Ordering as result are equivalent:

a<b && b<a  cannot occur due to asymmetry requirement on <
a<b && !(b<a)  <=> cmp(a,b)==Less
!(a<b) && b<a <=> cmp(a,b)==Greater
!(a<b) && !(b<a) <=> cmp(a,b)==Equal

The function cmp_by_age is not a total order on type Person, as it breaks the the antisymmetry rule ( If a ≤ b and b ≤ a then a = b ).
The function is a total order on the equivalence classes induced by Equal. That requires that Equal defines an equivalence relation, of course. So, for all a, b, c:

cmp(a,a) == Equal
if cmp(a,b)== Equal then cmp(b,a)==Equal
if cmp(a,b)==Equal and cmp(b,c)==Equal then cmp(a,c)==Equal

This is the concept that strict weak orderings is capturing.

22

Only for “strict weak ordering” and “total ordering”. If we talk about different kinds of ordering then they are not equivalent.

In particular, as was correctly noted by @jdahlstrom one couldn't simply compare floats to get the desired result.

23

Indeed. I meant strict partial order not weak. I was trying to provide an example of an “ordering” that is not reflexive (in the math sense) and which is also an ordering for floats. Not sure why I said weak when I haven’t much experience with that concept at all.

24

Yep, sorry for the confusion. You're correct that the ordering of floats is a strict partial order, which is something that I myself didn't realize. In that sense Rust's PartialOrd is aptly named. To clear up any remaining confusion, I'll go through the requirements of SPO:

  1. Irreflexivity: !(a < a) for all a.
    Obviously met by finite float values, and also met by NaNs, for which !(NaN op NaN) for all comparison operators op.

  2. Asymmetry: if a < b, then !(b < a).
    Obviously met by finites and vacuously true if a, b, or both are NaNs because the antedecent is then never true. Importantly this condition is just "if", not "if and only if".

  3. Transitivity: if a < b && b < c, then a < c.
    Again, obvious for finites, and vacuously true if any of a, b, c is a NaN.

[1]

  1. Lol, I realized this message sounds a lot like written by an LLM. So just for fun, I asked "does the standard ordering of IEEE floats constitute a strict partial order?" from Claude, ChatGPT, and DeepSeek. Only DeepSeek got it right without enabling reasoning, and ChatGPT also did when reasoning was enabled. ↩︎

25

Don’t even need item 2 since 1 and 3 imply it, but thanks for the proof.

26

I think there are some misunderstandings in this thread. Years ago I did an analysis and explanation of ordering terminology that I still refer to today, because the terminology is confusing, and the other online resources are not very illuminating. You might find that article helpful.

C++ (and Rust I presume) and most sorting algorithms really, truly, only require a strict weak ordering and not a total ordering over the values it is sorting. But it's understandable to think otherwise, since a strict weak ordering is just a total ordering over some function of the values (with the equivalence classes being the values for which the function has the same result), and because the distinction between strict weak and total evaporates if you can't compare the values for equality: then there's no way to observe that the equivalence classes contain distinct values. A total order is a strict weak order in which each equivalence class has only one element. If any of the foregoing isn't immediately apparent, read the article I referenced and I hope it will be clear.

There's another possible misunderstanding, too: it doesn't matter if the comparison is a strict weak ordering over all possible values of a type. Only the values being sorted matter. That was handled in the original STL documentation by talking about the domain of the operation, but it has since been lost in the C++ standard, leading to the idea (supported by standard language) that floats can't be sorted at all. But you can sort a collection of floats and get a meaningful result as long as it contains no NaNs.

Anyway, again, HTH.

27

Was that meant for me, or did you accidentally hit "Reply" on my post but intended to hit "Reply" at the bottom of the thread? I'm a little confused if it was actually meant for me since I was barely involved in this thread and only made a point to state that in math orderings do exist that are not reflexive (in particular strict orderings), and that < under floats is a strict partial ordering according to IEEE 754.

28

Of course. But we are discussing in the context of sorting. The C++ sort then
requires the less-than function to be a strictly weak ordering and the Rust
sort_by function talks about a total order.

I think the current wording in the sort_by documentation is meant to rule out
functions like cmp below

enum TieBreaker {
    Stone,
    Paper,
    Scissors,
}

impl TieBreaker {
    pub fn cmp(t1: &TieBreaker, t2: &TieBreaker) -> Ordering {
        // ensures that Stone < Paper, Paper < Scissors, Scissors < Stone etc.
       ...
    }
}

The compiler happily accepts a code like

let mut tbs = vec![Scissors, Paper, Stone, Paper, Scissors, Paper];
tbs.sort_by(TieBreaker::cmp);

But it is a logic error to make this call, because the cmp function is not transitive as is required by PartialOrd. When I ran this code, it returned
[Paper, Scissors, Stone, Paper, Paper, Scissors]
The documentation states that it also could have panicked. It doesn't state
that it could enter an infinite loop, although I think that should also be
allowed. In C++ speak, we would say that this leads to undefined behaviour.
For the implementor of the sort algorithm this basically means he may use this
precondition for proving that the implementation is correct.

So, the caller has to make sure that some preconditions are met that cannot be checked by the compiler. And once those preconditions are met, then the equivalence of using less than or a cmp function follow. That is what I meant in my previous post.

Coming back to my original question that started this thread. I think it is clear that the current wording of the sort_by is sloppy at least. And that referring to total orderings (which means more than a function returning an Ordering) is confusing.

29

To unspecified behavior. That is, it would do something that some other valid code could do in its place, not "anything at all".

30

Sorry, user error. I'm not very good at computers :wink: It was meant for the thread.

31

You are right. I shouldn't have used that phrase without looking it up. Undefined behaviour is more for cases that cannot occur in safe Rust (accessing memory that is not OK to access).

For me the bottom line for both undefined and unspecified behaviour is: don't go there.