Maybe the point is: If we demand that PartialOrd
was a partial order, then it must not be implemented by f64
. So in fact PartialOrd
describes something else.
Fun fact: if you “phrase” the partial order axioms in a particular way, i.e.
 if 𝑎 = 𝑏 then 𝑎 ≤ 𝑏
 if 𝑎 ≤ 𝑏 and 𝑏 ≤ 𝑎 then 𝑎 = 𝑏
 if 𝑎 ≤ 𝑏 and 𝑏 ≤ 𝑐 then 𝑎 ≤ 𝑐
(i.e. mostly reflexivity got written down in a more sophisticated, but equivalent manner)
then they suddenly become a legitimate way of describing PartialOrd
, if you just – syntactically – replace ≤
with <=
and =
with ==
, i.e.
 if
a == b
thena <= b
 if
a <= b
andb <= a
thena == b
 if
a <= b
andb <= c
thena <= c
Of course, this ignores the fact that the definition of “partial order” does assume “=” to be true mathematical equality and thus in particular an equivalence relation that’s concruent w.r.t. “≤”. (I.e. you can replace equal things with equal things on either side of the “≤”.)
I would like to rephrase what I tried to say earlier:
PartialOrd
could be used to describe a partial order. But then we also must implement PartialEq
in such a way that a == a
is always true. And then we could also mark our type as impl Eq
.
Hence, PartialOrd
is
not really defined in a good way to describe a partial order because it demandsPartialEq
but notEq
,implemented in cases when there isn't a partial order (such as forf32
andf64
).
Anyway, I'm still unsure.
We had a bit of a conversation about this back in Conversions: `FromLossy` and `TryFromLossy` traits by dhardy · Pull Request #2484 · rustlang/rfcs · GitHub
IIRC I ended up at the rule of a == b ⇒ a.clone() == b.clone()
, which works for f32
and anything else I can think of, though that's not sufficient in general and I think it can be at most a SHOULD since there might be types that don't meet it today.
I just noticed that:
Irreflexivity and transitivity together imply asymmetry. Also, asymmetry implies irreflexivity. In other words, a transitive relation is asymmetric if and only if it is irreflexive. So the definition is the same if it omits either irreflexivity or asymmetry (but not both).
(Strict partial order on Wikipedia)
So we need transitivity and either irreflexivity or asymmetry.
Let's try to show that PartialOrd
is a partial order:
Checking the docs on PartialOrd
, I don't see either irreflexivity or asymmetry. But there is a demand that a < b
if and only if b > a
:
The comparison must satisfy, for all
a
,b
andc
:
 transitivity:
a < b
andb < c
impliesa < c
. The same must hold for both==
and>
. duality:
a < b
if and only ifb > a
.
Now if we set b
to a
(which we can, because the "duality" must hold for all a
and b
), we get:
a < a
if and only if a > a
. Since PartialOrd::partial_cmp
cannot return both Some(Less)
and Some(Greater)
, we can deduce that a < a
is always false. Hence irreflexivity is fulfilled (and then also asymmetry), and we have a partial order. q.e.d.
Would you agree?
Eh.. alright, technically <
is a strict partial order here. But in the context of strict partial orders, the corresponding nonstrict partial order is gained by taking true equality into consideration, i.e. you define a ≤ b
by a < b  a = b
. In other words, the notion of “equality/equivalence” in the context of strict partial orders is mathematical equality, which is – in particular – an equivalence relation. (And also fulfills concruence axioms like: a = b
and b < c
and c = d
implies a < d
).
In Rust, there is not implicit, always present, alreadydefined true equality with these properties that we can use, so discussing the question of whether we have a strict partial order stops making all that much sense once we also want to have a corresponding ≤
relation. (Which we do want in the case of PartialOrd
; it’s the method le
after all.)
In other words: You cannot define ≤
from <
alone, when you have a strict partial order <
. Instead, you’d need to talk about the strict partial order <
and also the way it relates to the partial equivalence relation ==
. (You can define all the remaining operations in terms of these two.)
In order to get all the requirements of PartialOrd
, you need to add the following axioms in order to specify how <
and ==
interact:
 at most one of
a < b
,a == b
orb < a
is true (this axiom is present  implicitly  in thePartialOrd
docs, also this axiom immediately implies irreflexivity as you’ve noticed) 
a == b
andb < c
andc == d
impliesa < d
(i.e. the congruence axiom that is missing from thePartialOrd
docs)
Now, if you want to, you can verify that having a partial equivalence relation ==
and a strict partial order <
with these two additional axioms is cryptomorphic to having a single, arbitrary, reflexive relation ≤
,
using the definitions
(≤
in terms of <
and ==
):

a ≤ b
iffa < b  a == b
and
(==
and <
in terms of ≤
):

a == b
iffa ≤ b  b ≤ a

a < b
iffa ≤ b && !(a == b)
I.e. verify that using the axioms for <
and ==
described above^{1}, and the definition for ≤
, you can derive that ≤
is reflexive, and the definitions of <
and ==
in terms of ≤
are true; and viceversa, using a reflexive relation ≤
and the definitions of <
and ==
in terms of ≤
, verify that <
and ==
fulfill the axioms described above^{1}, and verify that the definition of ≤
in terms of <
and ==
is correct.
^{1}Those axioms were: <
is a strict partial order, ==
a partial equivalence relation, and the two additional axioms
 at most one of
a < b
,a == b
orb < a
is true 
a == b
andb < c
andc == d
impliesa < d
To justify my statement, let me cite Rust's reference (Comparison Operators):
a == b;
// is equivalent to
::std::cmp::PartialEq::eq(&a, &b);
I'm only skimming this thread, and you probably meant semantically, but that documentation is wrong, as discussed previously (for the standard lib docs).
Which is funny, of course, given that AFAIK the whole reason PartialOrd
exists is the IEEE 754 floatingpoint semantics. Is there even precedence for objects that behave like IEEE floats in mathematics? Are they weird enough to not match any moreorless commonly used terminology?
NULL
in SQL has similar semantics but seems more sane in that it embraces true threevalued logic: its "PartialEq" actually returns "Option<bool>" in Rust terms. So NULL == NULL
is neither true nor false, it is itself NULL
, as in unknown, just like NULL < NULL
.
Yes, I did find "partial preorder" which matches, as mentioned somewhere above in this thread.. ah here it is:
Admitted, one cannot really necessarily call this notion
if it isn't even (really, AFAICT) possible to find the definition in the English Wikipedia.
But alas, "reflexive relation" isn't too outoftheworld either, and that's apparently (according to my interpretation of the docs) what PartialOrd
is all about. Of course the alternative interpretation of "if you leave out this NaN
element, it's a total order, but NaN
is incomparable with everything and not even equal to itself" is a totally mathematical apt description.
Might be more sane; but note that (as far as my mathematical experience goes) threevalued logic is not generally the most common thing used in "mathematics". Your average mathematician would probably be happier with the "transitive relation" or even the "partial preorder".
I accidentally incorrectly simplified the second axiom. It has to be two separate ones

a == b
andb < c
impliesa < c

a < b
andb == c
impliesa < c
(I had applied a way of simplifying congruence that only legitimately works with actual equivalence relations, not with a partial equivalence relation. Sorry for that oversight.)
Also, I only just noticed that the first of those two (well, now three) axioms follows from the second one (or rather from the other two), using the axioms of "strict partial order".
Posting here instead of the other thread I forked, because this is related to the original question: "Why sort()
need T
to be Ord
?"
@kornel, how about something like:
trait PartialSort {
fn partial_sort(&mut self);
}
impl<T: std::cmp::PartialOrd> PartialSort for [T] {
fn partial_sort(&mut self) {
todo!()
}
}
This could be easily implemented in a crate, right?
That could work.
Rust also has a "hack" of implementing regular inherent min
/max
methods directly on floats, which syntactically mimic what Ord
has, so number.min(number)
works for both floats and integers.
How about doing the same hack for sort functions?
impl [f32] { // is that a real syntax? :)
fn sort_unstable(&mut self) {…}
}
"Partial sort" is unfortunately the name of a completely different algorithm that is not directly related to partial ordering. So the name is a nogo
We could name it .sloppy_sort
^^
so
number.min(number)
works for both floats and integers
But note that number.minimum(other)
was also just added (in nightly), for the other "minimum" defined in IEEE 754.
How about doing the same hack for sort functions?
I'm not really a fan, because you end up with the whole "well, where do the NANs go?" problem when defining said function. For example, do they go at the beginning or the end? And does the NAN payload matter?
I think having people do .sort_by(f32::total_cmp)
would be fine (once we eventually stabilize that, or something like it).
And note that it puts NANs at both ends, depending on their sign bits.
So, what does it mean to sort something by PartialOrd? It seems like a reasonable expectation that for any two indices i < j
, it holds that v[i].partial_cmp(v[j]) != Some(Greater)
. For the general (worst) case, consider sorting a haystack with two needles and a million pieces of hay in it:
NeedleA < NeedleB

PieceOfHay(k)
not comparable to anything but itself  Everything equal to itself
The needles have to end up correctly ordered, but the only way to get any useful information (including recognizing if it's a needle or not) is to compare the two needles to each other. Therefore we have to make O(n²)
comparisons!
What might happen in reality is that someone tries to sort a large array that accidentally ended up containing only NaN
s. If the algorithm is to be correct and generic for T: PartialOrd
, it may effectively hang the program at that point. Of course for actually sorting floats, f32::total_cmp
(or anything that can e.g. consider all NaNs equal) will have no issues.
Couldn't the algorithm just arbitrarily sort PieceOfHay
before any other value when applying quicksort to everything (which is O(n * log(n)), if I'm not mistaken?
Ah, PieceOfHay
is comparable to itself. That might make things more difficult.
The point is that in a T: PartialOrd
generic function the only thing you can do with a T
is to try to compare it to another T
. I suppose it could try something like examining the bit patterns, and if they match you know that the two things are interchangeable. But even that won't help if they never do match. It could equivalently be the integers 0..n
with two randomly chosen as the needles. The algorithm can't know which ones they are until it finds both at the same time and compares them.
Floats are saved by the property that the incomparable elements (NaN
s) are not comparable to anything, but that's not required by PartialOrd
.
So, what does it mean to be partially sorted?
Note that when I hear "partial sort" I think std::partial_sort  cppreference.com, which is different from "allows partial ord".
The needles have to end up correctly ordered, but the only way to get any useful information (including recognizing if it's a needle or not) is to compare the two needles to each other. Therefore we have to make
O(n²)
comparisons!
I looked up this kind of question earlier, this page contains interesting links
https://stackoverflow.com/questions/4600258/sortingaposet
the first answer cites a paper that contains algorithms that are more efficient depending on a parameter "w" which is (AFAIR) something like the largest size of a set of mutually uncomparable items.
On the other hand, if very few items are comparable at all (and you somehow know beforehand which are) then topological sort might be efficient; otherwise a O(n²)
time might be correct for the best possible approach, in a fully general setting.