Why `sort()` need `T` to be `Ord`?

IMO, Ord is definitely a trait for weak orders. It's just incorrectly documented (it should say "total preorder", yet it does say "total order" im the docs). Look at Eq which is correctly documented as a trait for equivalence relations, not for equality. The distinction between stable and unstable sorting algorithms only really makes sense for weak orders, too. (The German version of the Wikipedia article also does point that out.)

(The use of "total order" in the docs makes some sense if the equivalence by the Eq implementation is (mis-)interpreted as equality. After all, a total preorder is the same as an actual total order on the equivalence classes.)

3 Likes

Because that was before C++20. I'm not joking.

GCC got the appropriate optimization only very recently, I wouldn't be surprised that LLVM was also missing it at the time when bug was created.

According to the documentation, Ord is a total order. That also makes sense to me, because it will always compare an element to another element as either being smaller or greater, unless it is equal.

Isn't a weak order the same as a total order if we simply put all non-comparable items in the same equivalence class? Maybe these two are actually the same and it's just a semantic difference?

Now I'm confused

But I just noticed that a "total order" indeed depends on how equality is defined (or a used equivalence relation). And the Ord trait does require that equality (or a certain equivalence relation defined through Eq) does behave in a certain way.

Yes, Eq could be any equivalence relation.

Now the question is… Is the equality / non-equality operator here an arbitrary equivalence relation? I would say yes, because we're not operating with numbers or any particular objects here in the mathematical definition. If yes, then I'd say Ord can be seen as "total order".

My point is: Ord interacts with Eq, and thus I'd say it's correct to describe it as total order.

I would say:

• Ord unambiguously sorts all elements (unless some elements are equal to one another according to Eq, in which case their sorting can vary).
• WeakOrd (which doesn't exist) could treat some elements as "equal in regard to the sorting", independently on how Eq (== operator) is defined for that type.
• PartialOrd can treat some elements as "could appear anywhere in the list". Floating point numbers have a partial order, because NaN could appear anywhere in a sorted list.

No, it's not an arbitrary equivalence relation.

Mathematical notion of equality is defined for all mathematical objects. On a fundamental level in first-order logic you already have a notion of equality. It asserts basic properties like the ability to always being able to substitute equal things with equal things in statements or expressions. This it related to the notion of equality by Leibniz which basically says that things are equal if and only if they have the same properties. Or if you take a set theoretic foundation, that comes with a more concrete notion of equality by means of sets having the same elements.

Docs actually use both terms in the first statement:

Trait for equality comparisons which are equivalence relations.

I think there are two levels of description here:

• on the representation level, it's an equivalence relation
• on a higher, semantic level, it's equality

Ah okay! I guess you're right then.

In that case, either Eq would need to be redefined as "equality" (instead of "equivalence relation") or Ord would need to be redefined as "weak order" (instead of "total order").

Do I understand it correctly?

For instance:

Two Vec with different capacities but same sequence of values have different bit representations underneath, but represent the same mathematical object.

== implements the equivalence relation on representations, but it also means equality on the mathematical objects that are represented.

To give everything a name (feel free to point out mistakes)

PartialEq - partial equivalence relation
Eq - equivalence relation
PartialOrd - partial preorder (hard to find on English Wikipedia) Edit: that's not quite right...
PartialOrd + Eq - preorder
Ord - total preorder

(I'm ignoring S: PartialEq<T> or S: PartialOrd<T> between different types. Those are hard/impossible to characterize.)

Thanks for sharing, I'll look into that later. I have a preliminary comment already:

If I understand it right, then a "total preorder" is a weak order, and as such it doesn't need any equivalence relation being defined (but Ord does). (Even though you could derive an equivalence relation from a weak order, of course.)

I also noted @tczajka's comments that == often means equality when used with mathematical objects.

I'll look into it later again. Thanks for all your feedback so far!

Double-checked, turns out, no. The closest thing to the axioms given for PartialOrd in the docs is just:

<= is transitive

Yup, that's it. You can define the rest:
a == b iff a <= b && b <= a
a != b iff !(a == b)
a < b iff a <= b && a != b
a > b iff b < a
a >= b iff b <= a

But it appears there's actually an axiom missing in the documentation of PartialOrd. It doesn't state anywhere that a < b and b == c implies a < c (or similarly for a == b and b < c, giving a < c). That's most likely an oversight though, I doubt that's intentional. If you add those two implications, the characterization becomes truly equivalent to “<= is transitive”.

For the record, f32 and f64 do actually form partial preorders. They do fulfill the additional constraint that a <= b implies a <= a and b <= b. (Called "partial reflexivity", or "reflexivity where the relation is defined" in the German Wikipedia article.) So if PartialOrd is just about giving a trait that floating point numbers can implement, then "partial preorder" rather than "transitive relation" would've been a valid choice, too.

I'm unsure. Let me look at what @tczajka brought up:

But in PartialEq we find:

Trait for equality comparisons which are partial equivalence relations.

Now the mathematical "equality" (if I understand it right) is always an equivalence relation and never a partial equivalence relation. That is because equality is reflexive (see basic properties of equality).

So perhaps the term "equality comparisons" should be (or needs to be) interpreted more sloppy here.

Also note that there is no comma after "comparisons". The reference obviously refers to two different "equality comparisons" here (i.e. not "the" equality in the mathematical sense).

Following these thoughts, I'd say @steffahn is right with:

Now to the other traits:

Let's take a look at the return value of PartialOrd::partial_cmp, which is Option<Ordering>, where Ordering can be Less, Equal, or Greater.

Now that's pretty different from what a partial order is in the mathematical sense, which is only a binary relation (i.e. partial_cmp should return a bool, if we stick to the mathematical definition). Let's look at the properties of a partial order. A partial order requires:

I would say PartialOrd is a trait that denotes there is a partial order and(!) a partial equivalence relation (with some restrictions). This is also reflected by the supertrait: PartialOrd<Rhs = Self>: PartialEq<Rhs>.

Note that PartialOrd::partial_cmp's return type has four different values:

• None
• Some(Less)
• Some(Equal)
• Some(Greater)

Along with the result of PartialEq::eq, we have eight possible results for (a.eq(&b), a.partial_cmp(&b)) (of which only four are legit):

• (false, None) (allowed)
• (false, Some(Less)) (allowed)
• (false, Some(Equal)) (forbidden)
• (false, Some(Greater)) (allowed)
• (true, None) (forbidden)
• (true, Some(Less)) (forbidden)
• (true, Some(Equal)) (allowed)
• (true, Some(Greater)) (forbidden)

This seems to fit the observation that we have two binary relations, which would result in 4 possible outcomes.

(Edit: There is a flaw in my reasoning, see @steffahn's response below.)

Let's put this together, assuming our partial equivalence relation is == and the partial order relation is ≤.

• If a == b and ab, we get (true, Some(Equal)).
• If a == b and not ab, we get…
• If a != b and ab, we get (false, Some(Ordering::Less)).
• If a != b and not ab, then (false, Some(Ordering::Greater)).

The problem here is the second case. Now I'm really confused. I suspect that PartialOrd thus isn't actually a partial order. I suspect that PartialOrd's consistency rules make PartialOrd inconsistent with the mathematical definition of a partial order.

Or maybe I overlooked something? Sorry if I caused more confusion, but I feel like there is something wrong.

So do I understand right that if the missing axiom was added, then PartialOrd is partial preorder?

I.e. PartialOrd isn't a partial order then, just like I suspected in my previous post?

No, the missing axioms “a < b and b == c implies a < c” and “a == b and b < c implies a < c” are necessary in order to ensure that <= is transitive. The partial preorder would furthermore require this

Note that, if you assume that PartialOrd only defines <= and all other comparisons are defined in terms of <= as I explained above

Then the

for partial_cmp are nothing more than the four different results of testing both a <= b and b <= a.

a <= b b <= a PartialOrd::partial_cmp(&a, &b)
true true Some(Equal)
true false Some(Less)
false true Some(Greater)
false false None

No, indeed not a partial order. The main point is that PartialOrd doesn't require reflexivity for <= (since it doesn't even require reflexivity for ==).

2 Likes

I forgot that I can swap a and b, thus I need 4 results for a single binary relation already. Sorry for the confusion.

So PartialOrd is just a transitive relation then. Having to provide an implementation of PartialEq is merely an implementation detail (assuming you'd add the missing axioms).

Adding reflexivity would create a preorder, as you said:

And Ord would indeed be a total preorder like you said:

Which is the same as a "(non-strict) weak order", I think. Which, in turn, is cryptomorphic to a "strict weak order".

So summarizing it:

• PartialEq - partial equivalence relation
• Eq - equivalence relation
• PartialOrd - a transitive relation (requires implementing PartialEq such that if a <= b && b <= a, then a == b)
• PartialOrd + Eq - preorder
• Ord - total preorder or weak order (depending on p.o.v. / semantics)

Is that right?

yup

In terms of axioms:

transitive + symmetric: == in PartialEq
transitive + symmetric + reflexive: == in Eq
transitive: <= in PartialOrd
transitive + reflexive: <= in PartialOrd + Eq
transitive + reflexive + total: <= in Ord

1 Like

Then you're right that the documention of std::cmp is pretty imprecise / wrong.

Wow, the overview in std::cmp is kind-of sad; it doesn't even get Eq right anymore:

This module contains various tools for ordering and comparing values. In summary:

• Eq and PartialEq are traits that allow you to define total and partial equality between values, respectively. Implementing them overloads the == and != operators.
• Ord and PartialOrd are traits that allow you to define total and partial orderings between values, respectively. Implementing them overloads the < , <= , > , and >= operators.
• Ordering is an enum returned by the main functions of Ord and PartialOrd , and describes an ordering.

Well, at least it just calls it “equality”, which – to be fair – might be the right term in Rust context, since it's used to overload the “equality” operator.

You mean because it would need to say "equivalence relation" instead of "total equality"?

IDK, I guess the worst part is actually that it calls PartialOrd “partial ordering”, which is so far off that it cannot even be rectified: For Eq and Ord at least the description as “equality” and “total order” is “correct” if you interpret “equivalence” as “equality”, e.g. by reasoning about equivalence classes.

As you pointed out (before editing your comment) “partial equality” is a strange term, too, but at least it’s not misleading.