ordered_float - Rust
Wrappers for total order on Floats. See the [`OrderedFloat`] and [`NotNan`] docs for details.
To give a concrete example how <=
's transitivity is missing in the currently documented axioms:
#[derive(Copy, Clone)]
pub enum O { A, B, C }
use O::*;
use std::cmp::Ordering::{self, *};
impl PartialOrd for O {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
match (*self, *other) {
// all values equal themselves, A == B
(A, A) | (B, B) | (C, C) | (A, B) | (B, A) => Some(Equal),
// B < C
(B, C) => Some(Less),
(C, B) => Some(Greater),
// A and C not comparable
(A, C) | (C, A) => None,
}
}
}
impl PartialEq for O {
fn eq(&self, other: &Self) -> bool {
self.partial_cmp(other) == Some(Equal)
}
}
impl Eq for O {}
fn main() {
// violating congruence
assert_eq!(A == B, true);
assert_eq!(B < C, true);
assert_eq!(A < C, false);
// or
// violating `<=`'s transitivity
assert_eq!(A <= B, true);
assert_eq!(B <= C, true);
assert_eq!(A <= C, false);
}
this enum fulfills1 all the axioms listed in the documentation for PartialEq
, PartialOrd
and even Eq
, yet behaves quite surprisingly lMO.
@jbe, looking at this example, turns out that without fixing the documentation of PartialOrd
, we don't even get that PartialOrd + Eq
is a preorder (or "intuitively a partial order, if we take Eq
as equality").
1Going through the axioms: The definition obviously defines an equivalence relation that identifies A
and B
. (==
is reflexive, transitive, symmetric.) The axioms listed as "ensured by the default implementation" on PartialOrd
's docs are also fulfilled, and "a == b
if and only if `partial_cmp(a, b) == Some(Equal)`` is true by definition.
This leaves:
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
.
This transitivity is true. The only instance of ... < ...
is B < C
, so there's no way to fulfill the precondition a < b
and b < c
for some a
, b
, c
, in the first place. And duality is also true, since the only instance of ... > ...
is C > B
, which corresponds to the only instance of ... < ...
being B < C
It also helps me to understand that I can use
PartialOrd
to implement a partial order, but it will confuse me if I'm suddenly surprised by>=
and<=
not acting accordingly.
The map is not the territory. Here's an implementation consistent with the requirements as I read them.
struct Snowflake(i32);
impl PartialEq<Self> for Snowflake {
fn eq(&self, _: &Self) -> bool {
false
}
}
impl PartialOrd<Self> for Snowflake {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
match self.0.cmp(&other.0) {
std::cmp::Ordering::Equal => None,
ne => Some(ne),
}
}
}
For Snowflake
, <=
is a strict partial order (it's the same as <
), not a non-strict one.
And yeah, it is kinda funny that
PartialOrd
was likely introduced because of IEEE 754. Or were there other reasons?
Yeah, that's why. I think I saw the specific bug in passing when looking it up the stuff below, but didn't note it. There was no split until 2013 or 2014 or such.
I thought maybe the fact that PartialOrd<_>
(and PartialEq<_>
) can also compare different types might have something to do with it. But no. Turns out that there used to be a different trait (Equiv
) for cross-type equality, but they got merged together. Before that, none of the comparison traits were cross-type.
Interestingly, the motivator for Equiv
didn't need it anymore (replaced by Borrow
I guess), but the generic partial comparison traits got some takers in the standard lib. Also interesting is that Eq
and Ord
were also briefly made generic, but that got dropped in the stabilization PR. The PR says that the traits match the reform RFC but that's not true (since the type parameter was dropped from Eq
and Ord
), if anyone wants to take it up .
A related todo is still open and just got pinged by Mara, which is amusing timing.
What is an example of a practical problem that would be caused if Eq
was automatically implemented whenever PartialEq<Self>
was implemented? I don't really see any practical reason to separate these.
Reading on the requirements, PartialEq<Self>
already requires symmetry and transitivity. Eq
adds a requirement for reflexivity. But reflexivity of a relation R can be written as:
a = b => R(a, b)
Which, for equality, is a tautology:
a == b
=> a == b
As a practical example, I see that HashMap::get
requires Eq
for keys. But would any problem be caused if you used f64
for hash keys? I don't think so. Every NaN would simply be treated as a separate, unequal key, so every time you insert NaN you get another entry, and every time you look up NaN you don't find anything. So what? Seems fine to me, that's consistent with how equality works for NaN.
There is a problem with implementing Hash
for NaN in a good way though, because really it should be different every time. But that's an issue separate from Eq
.
To give a concrete example how
<=
's transitivity is missing in the currently documented axioms: […]
Thank you very much, it makes things much easier to grasp.
I totally agree that <=
not ending up transitive is odd. And I'm not sure if that was intended or not to allow this.
However, I would like to give a counter-argument why it could (maybe) (perhaps) make sense in some cases to demand that <
and >
describe a partial order while <=
and >=
aren't transitive.
(I hope I don't make any logic error here.)
Whenever we implement PartialEq
without Eq
, this means our ==
operator doesn't mean "equality". It means ==
is some other weird "partial equivalence relation". I also showed that PartialOrd
gives us a strict partial order regarding <
and >
.
Now let's consider a new floating point type where:
==
, <
and <=
) as usual (e.g. −2.3 <
−1.0 <=
−1.0 <
6.2).==
(as it can make sense to treat these equally / as equivalent, as for example done on the Riemann Sphere in mathematics or in the context of negative (Kelvin) temperatures).<
and >
).I could imagine a complex number type where we want to include −∞ and +∞ as sort-of-limit for some calculations such as 1.0 / 0.0
, but treat −∞ ==
+∞, yet −∞ <
0 <
+∞. This doesn't sound more "odd" what IEEE 754 does.
We might still define a partial order on such type, e.g. where <
may only return true if the imaginary part is zero.
(Side note: I really dislike that IEEE 754 distinguishes between −∞ and +∞, and even between −0 and +0, despite −0 ==
+0.)
fn main() { // violating congruence assert_eq!(A == B, true); assert_eq!(B < C, true); assert_eq!(A < C, false); // or // violating `<=`'s transitivity assert_eq!(A <= B, true); assert_eq!(B <= C, true); assert_eq!(A <= C, false); }
Let's say
A
represents +∞B
represents −∞C
represents zero.Then we get:
==
−∞ is true (like on the Riemann Sphere)<
0 is true<
0 is false<=
−∞ is true (because +∞ is either smaller than or equivalent to −∞)<=
0 is true (because −∞ is either smaller than or equivalent to 0)<=
0 is false (because +∞ is neither smaller than nor equivalent to 0)This doesn't seem more crazy (to me) than what IEEE 754 does. What do you think?
I would think of x <= y
simply as a short-hand for x < y || x == y
, and not more and not less. I don't think we should impose any semantics on <=
but keep it strictly formal. Following that, PartialOrd
describes a partial order (regarding <
and >
) and PartialEq
describes a partial equivalence relation (regarding ==
and !=
).
P.S.: Of course, PartialOrd
and PartialEq
are somewhat intertangled, because PartialEq
is a supertrait of PartialOrd
, but I consider this merely as an implementation detail (it allows to provide optimized implementations for PartialOrd::le
, for example).
From a developer perspective: I have arrays of floats, and I need them sorted. I don't care what the proper math says, I have floats, not real numbers. Rust's sound and tight definitions are not helping me when I need to sort floats, and I can't.
The current state simply prevents me from getting my job done. I need to put extra work to do exactly the "bad" thing that Rust is trying to stop me from doing. I use sort_by(partial_cmp().unwrap_or(Equal))
or wrap floats in a newtype that intentionally incorrectly implements Ord
just so that I can get floats sorted.
Could we have sort()
functions that use a trait like Comparable
and work on anything that supports <
, while accepting and permitting all of the consequences of this comparison being inconsistent?
From a developer perspective: I have arrays of floats, and I need them sorted. I don't care what the proper math says, I have floats, not real numbers. Rust's sound and tight definitions are not helping me when I need to sort floats, and I can't.
The current state simply prevents me from getting my job done. I need to put extra work to do exactly the "bad" thing that Rust is trying to stop me from doing.
I have had the same problem. I always end up with something like:
/// Compare two [`f64`] numbers while treating [NaN](f64::NAN) as greatest.
pub fn cmp_f64_nan_greatest(a: f64, b: f64) -> std::cmp::Ordering {
a.partial_cmp(&b).unwrap_or_else(|| {
a.is_nan().cmp(&b.is_nan()).then(std::cmp::Ordering::Equal)
})
}
And then using that in a closure passed to sort_by
.
It's annoying. I agree.
I use
sort_by(partial_cmp().unwrap_or(Equal))
or wrap floats in a newtype that intentionally incorrectly implementsOrd
just so that I can get floats sorted.
That I don't do. I'm always worried NaN's could actually appear.
Could we have
sort()
functions that use a trait likeComparable
and work on anything that supports<
, while accepting and permitting all of the consequences of this comparison being inconsistent?
How about partial_sort
, which is happy with PartialOrd
? (Maybe I shouldn't have made a new thread, will be more careful next time, as these topics are kinda related.)
P.S.: I just gave an outline of an example in the other thread, as this is related to the original question: "Why sort()
need T
to be Ord
?"
The current state simply prevents me from getting my job done.
I agree. I have dealt with floating point professionally a lot, and have never seen any good coming out of the weird NaN comparison rules, it's always seen as an unpleasant nuisance.
Now let's consider a new floating point type [...]
There are proposals that fix many issues with IEEE-754, such as posits. They have no -0.0, no NaNs at all, better handling of denormals / precision, and only one ∞ (I'm not sure about that last one, I kind of like -∞, +∞ as initializers for minimum / maximum).
I have dealt with floating point professionally a lot, and have never seen any good coming out of the weird NaN comparison rules, it's always seen as an unpleasant nuisance.
I don't agree here, because in C I sometimes rely on NaN not being greater or smaller than any other number, for example.
Like when I write (in C):
if !(a > 0.0 && a < 1.0) error();
I think similar would apply in Rust. But you need to be careful to not "simplify" that to:
if (a <= 0.0 || a >= 1.0) error();
I don't agree here, because in C I sometimes rely on NaN not being greater or smaller than any other number, for example.
Like when I write (in C):
if !(a > 0.0 && a < 1.0) error();
I think similar would apply in Rust. But you need to be careful to not "simplify" that to:
if (a <= 0.0 || a >= 1.0) error();
Both of these would call error
if NaN was smaller than all other numbers. Wouldn't that be better than the current behavior, where the first one calls error
but the second one doesn't?
Both of these would call
error
if NaN was smaller than all other numbers. Wouldn't that be better than the current behavior, […]
If NaN is always smaller than any number, then this doesn't work:
if (a < 0.0) { /* negative */ }
else if (a >= 0.0) { /* non-negative */ }
else { /* something bad happened! */ }
If f64::NAN < 0.0
, then a < 0.0
would be true (which is somewhat odd).
I have worked with systems where NaN is "sorted" in some way (I don't remember where, maybe it was SQL?), and it didn't feel good.
Regarding workarounds for floats, there's an obligatory mention of
Wrappers for total order on Floats. See the [`OrderedFloat`] and [`NotNan`] docs for details.
missing in this thread.
The crate supports two legitimate approaches with wrapper-types: Either define an order for NaN
(in this case arbitrarily, as the greatest element), or disallow NaN
entirely (which is checked when constructing the wrapper type).
if (a < 0.0) { /* negative */ } else if (a >= 0.0) { /* non-negative */ } else { /* something bad happened! */ }
If
f64::NAN < 0.0
, thena < 0.0
would be true (which is somewhat odd).
Odd perhaps, maybe positive NaNs are more intuitive than negative NaNs
The positive/negative example shows why NaNs are a nuisance and it would be better if they didn't exist at all. After all, i32
doesn't have NaNs (even if you divide 0/0), and it works out fine.
But the code you wrote is weird. If you simply forgot about NaNs it would be more natural to write:
if a < 0.0 { /* negative */ }
else { /* positive */ }
The only reason to write something like you wrote is if you remember about NaNs and want to deal with them separately. But in that case it's more natural to write:
if a.is_nan() { /* NaN */ }
else if a < 0.0 { /* negative */ }
else { /* positive */ }
I use
sort_by(partial_cmp().unwrap_or(Equal))
or wrap floats in a newtype that intentionally incorrectly implementsOrd
just so that I can get floats sorted.
I think that's a bad approach; this kind of sort_by
call does not meaningfully sort the list in the presence of NaNs. E.g.
use std::cmp::Ordering::Equal;
fn main() {
let mut list = [
3.0,
6.0,
9.0,
f64::NAN,
2.0,
5.0,
8.0,
f64::NAN,
1.0,
4.0,
7.0,
];
list.sort_by(|x, y| x.partial_cmp(y).unwrap_or(Equal));
dbg!(&list); // order unchanged, definitely not sorted at all, though
}
If you want to meaningfully sort a list of floats with NaNs, it's better to properly implement Ord
for a wrapper type, and instead disregard IEEE. Or to disallow NaNs alltogether. I.e. either of the approaches offered by the ordered_float
s crate.
Unless you're saying that you only use this "sort_by(partial_cmp().unwrap_or(Equal))
" if you already checked the list for NaN
s and there were none, but you don't like wrapper types; in which case you might as well use "sort_by(partial_cmp().unwrap())
" though.
But with IEEE 754, I can write:
if (a < 0.0) { /* negative */ }
else if (a >= 0.0) { /* non-negative */ }
And that's something, which I like about them.
I also do like NaN. If we have something like 0.0 / 0.0
, what can we do?
Neither of that is nice. Not sure though if NaN != NaN is a good idea. (But it's what we have.)
But with IEEE 754, I can write:
if (a < 0.0) { /* negative */ } else if (a >= 0.0) { /* non-negative */ }
And that's something, which I like about them.
You wouldn't write such code with i32
. The reason you wrote that is because you want to detect NaNs. I don't understand why you prefer the "redundant" comparison with 0.0 to detect NaNs rather than using is_nan()
which is a more direct way to say it, and thus nobody would be confused and think the comparison is redundant.
If we have something like
0.0 / 0.0
, what can we do?
- panic?
- give a wrong result such as zero?
I would say: return infinity, just as you would when any other number is divided by 0.0. Seems reasonable.
If you're dividing two numbers that have both just rounded to 0.0, the accurate answer could be anything, so it doesn't really matter what you return (except panic, you don't want panic).
@jbe, looking at this example, turns out that without fixing the documentation of
PartialOrd
, we don't even get thatPartialOrd + Eq
is a preorder (or "intuitively a partial order, if we takeEq
as equality").
This is a stronger argument. If Eq
denotes equality (which is a consequence of Ord
being a total order), then PartialOrd + Eq
should be a partial order in regard to <=
and >=
(I think).
But I think when a type is !Eq
, then <=
and >=
don't need to be transitive, as explained here:
I would think of
x <= y
simply as a short-hand forx < y || x == y
, and not more and not less. […]
When a type is !Eq
, then ==
doesn't denote "equality".
I would say: return infinity, just as you would when any other number is divided by 0.0. Seems reasonable.
That way, we couldn't distinguish this case (0.0 / 0.0
) from infinity (as a result of 1.0 / 0.0
) with .is_nan
. We only would have .is_infinite
, which means we lose information of the "failed computation".
Anyway, NaN has other issues, I think. I remember the -ffast-math
switch of C compilers which breaks IEEE 754 rules to make code faster.
Also this is odd:
fn main() {
let a = 0.0;
let b = -0.0;
assert_eq!(a, b);
assert_ne!(1.0/a, 1.0/b);
}
That way, we couldn't distinguish this case (
0.0 / 0.0
) from infinity (as a result of1.0 / 0.0
) with.is_nan
Yes but in practice there is no real reason why 1.0 / 0.0
needs to give a different answer from 1.0 / (-0.0)
, or why 0.0 / 0.0
needs to give a very different answer from 1e-300 / 0.0
.
When you have a calculation that results in 0.0 / 0.0
, and you're relying on it returning NaN, then you'll very likely run into the problem of rounding errors, which result in 1e-300 / 0.0 = inf
, or 0.0 / 1e-300 = 0.0
.
So this NaN result is not very reliable, and not a useful thing to depend on in practice.
Yes but in practice there is no real reason why
1.0 / 0.0
needs to give a different answer from1.0 / (-0.0)
, or why0.0 / 0.0
needs to give a very different answer from1e-300 / 0.0
.
I disagree. There is:
fn main() {
assert_eq!(f64::exp(-1000.0), 0.0);
assert_eq!(-f64::exp(-1000.0), 0.0);
assert!(1.0 / f64::exp(-1000.0) > 0.0);
assert!(1.0 / -f64::exp(-1000.0) < 0.0);
}
When you have a calculation that results in
0.0 / 0.0
, and you're relying on it returning NaN, then you'll very likely run into the problem of rounding errors, which result in1e-300 / 0.0 = inf
, or0.0 / 1e-300 = 0.0
.
I agree, it's not "reliable".
So this NaN result is not very reliable, and not a useful thing to depend on in practice.
I wouldn't depend on it, but it's still nice to have it as an indicator that something went wrong. It often helped me, at least during development. Maybe it's less useful when building a --release
.