# Why does ParitialOrd require consistent Equality

I am trying to wrap my head around the requirement of PartialOrd to be consistent with PartialEq and would appreciate some help to clear that

On the documentation of PartialOrd, the following is the first condition for consistency:

1. `a == b` if and only if `partial_cmp(a, b) == Some(Equal)`.

I am unable to understand why should `partial_cmp(a, b) == Some(Equal)` imply that `a == b`.

For instance, I can have a struct `Person(name, age)`, where the equality (to check duplicates) of the Persons could be on the `name`, whereas ordering of these could be on `age`.

To test this, I wrote a toy example to see how an inconsistent Ord vs Eq impacts things, and it does result in unexpected behavior:

The following code inserts two different Persons (different names) having the same age into a BtreeSet. But the set deduplicates these due to having the same age:

Prints:
`Person { name: "John", age: 30 }`

``````use std::cmp::Ordering;

#[derive(Eq, Debug)]
struct Person {
name: String,
age: u8,
}

impl PartialEq<Self> for Person {
fn eq(&self, other: &Self) -> bool {
self.name.eq(&other.name)
}
}

impl PartialOrd<Self> for Person {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}

impl Ord for Person {
fn cmp(&self, other: &Self) -> Ordering {
self.age.cmp(&other.age)
}
}

#[test]
fn testBtreeSet() {
use std::collections::BTreeSet;
let mut set = BTreeSet::new();
set.insert(Person {
name: "John".to_string(),
age: 30,
});

set.insert(Person {
name: "Jack".to_string(),
age: 30,
});

set.iter().for_each(|person| {
println!("{:?}", person);
})
}
``````

I think it's required to keep the `<`, `<=`, `==`, `>=`, `>` operators consistent.

Side note which doesn't apply to your question in particular: I have been proposing a change to the documentation (PR #103046) to clarify some things regarding these operators and the corresponding traits.

1 Like

I think you have actually found the answer.

Which is perfectly correct and acceptable way of doing things except if you then want to use such type with standard containers.

Why is that unexpected? You have violated the contract, you get some random behavior. GIGO at it's finest.

AFAICS there are no memory corruption or any other unsoundness which means everything works as expected.

1 Like

I think you have actually found the answer.

Actually, I still do not understand why should PartialOrd trait requires PartialEq and what is the reason for this strong consistency between the two.

Which is perfectly correct and acceptable way of doing things except if you then want to use such type with standard containers.

Do these standard containers explicitly specify which of the PartialEq or PartialOrd methods they would be used to order and dedup elements? I could have overlooked that in the document and it would be great to get a link to those! One of the main reasons to implement these traits is so that we can use standard algorithms and containers on these.

Why is that unexpected? You have violated the contract, you get some random behavior. GIGO at it's finest.

This is unexpected to me given my thinking that "sameness" and ordering were not completely consistent things (two different things can still be ordered at the same level). I am not trying to say that Rust language itself is incorrect.

If `PartialOrd` and `PartialEq` are inconsistent, then, for example, the following could be violated:

`a <= b` if and only if `a < b || a == b`

If this was violated, this would make code very difficult to read. I think it would be possible to relax this implication (in a hypothetical version of Rust), but not sure if that would make things better.

An example, but not sure if it's a good one:

``````use std::cmp::Ordering;

struct Crazy;

impl PartialEq for Crazy {
fn eq(&self, _other: &Self) -> bool {
false
}
}

impl PartialOrd for Crazy {
fn partial_cmp(&self, _other: &Self) -> Option<Ordering> {
Some(Ordering::Equal)
}
}

fn main() {
let a = Crazy;
let b = Crazy;
if a <= b && a >= b {
println!("this is true");
}
if a == b {
println!("if the previous was true, this should be true too, but it's not");
}
}
``````

Particularly other data structures may rely on `<`, `<=`, `==`, `>=`, and `>` being consistent. I.e. if they are not, then your `HashMap` or similar data structures could leak memory or do other bad stuff.

Note that it isn't a solution to only rely on `PartialOrd` in such data structures, because `partial_cmp` might be more expensive than `eq`. So it makes sense to use `eq` where possible, and to expect it being consistent with `partial_cmp`.

1. As long as inconsistencies don't result in UB because `PartialOrd` and `PartialEq` are not `unsafe` traits, so any mistake in their implementation must not result in UB. Further note that you must not even rely on `PartialEq` being consistent with itself in `unsafe` code, i.e. if `PartialEq` just returns random results, then `unsafe` code must still not cause UB. ↩︎

1 Like

Why should they? Partial equality and partial order are well-defined math concepts and are described in, literally, hundreds of computer-science related books (and also on Wikipedia, in brief form).

Rust just reused some of these achievments via it's standard library. Rules are additionally duplicated in the documentation for `PartialOrd`.

Rust documentation is not catch-all-for-all-knowledge-known-to-manking. It tries to do brief explanation for some concepts but, ultimately, can not be replacement neither for discrete math course nor for computer science course. And both of these courses, of course, include explanations and deifinitions for partial equality and partial order.

It's true that one may imagine different language where partial equality and partial order have no relation to each other, but experience have shown that this approach violates principle of least astonishment: most people would assume that if `x ⩽ y` and `x ⩾ y` then `x == y` and thus Rust's standard library requires that type of consistency, too.

Now, because this trait if not `unsafe` standard containers have to accept mistakes in their definitions (soundness pledge is still in effect even if your `PartialEq` and `PartialOrd` literally return random answers!). This places additional restrictions on implementation but the rule is, usually: if laws of partial order are obeyed then result is predictable, if they are violated then GIGO principle is in effect.

Yes. And standard algorithms (from computer science books, not Rust books!) require certain behaviors from partial order. Rust implementations, additionally, have to deal with extra complications for when rules are violated, but this is done only to the extend of GIGO: memory corruption is not Ok, but everything else is a fair game.

Not in discrete math and not in computer science. True, many sets can have more than one order, but Rust dictates that `PartialEq` and `PartialOrd` must declare precisely one. If you need more then one then you can use newtype pattern, or, for some container and algorithms, pass additional function to sort elements, etc… but `PartialEq` and `PartialOrd` must describe precisely one relation.

1 Like

What is "partial equality"? I don't think this is a well-defined math concept. See also PR #103046.

It's extremely well-define concept, going back to XIX century and before.

The issue that PR discusses is issue of therminology and that's where I'm afraid I would have to bail out: while I have mathematicians diploma and may talk about these things perfectly well… my university wasn't using English and thus I may very well mix some precise terms if I'll try to discuss these issues.

Good enough for the forum or blog post, not enough to vouch for proper terms in the documentation.

I'm afraid you would need to find someone who is good both in math and English simultaneously to go further with that PR.

Could you provide a reference (if you have one)?

Are you sure you don't mean "partial equivalence" instead of "partial equality"?

P.S.: I just saw you linked the same Wikipedia article, so maybe you meant "partial equivalence". Actually that's what the documentation should say (instead of "partial equality", which, in my opinion, isn't well defined).

It does.

I could try to find something from Cantor, but it would be in German, obviously.

Is there are difference? I think you have switched from math theory to something entirely different now.

Over the course of over 150 years math terminology was changing significantly. More: different authors used slightly different notions and names for the same things!

Which, essentially, means: math related to partial equivalence/pertial quality/partial equivalence relation is very old and extremely well-established, but the same couldn't be said about terminology.

And as I have said I'm just the wrong guy to discuss terminology.

It also says:

This trait allows for partial equality, […]

And I feel like "partial equality" isn't well-defined. At least not in mathematics (but I may be wrong).

Update: Also see `std::cmp` which says:

`Eq` and `PartialEq` are traits that allow you to define total and partial equality between values, respectively.

So what is "total equality"? (opposed to just "equality")

I think there is a difference between an "equivalence relation" and "equality". There are even different symbols for it (≡ vs =). Equality is an equivalence relation, but not every equivalence relation corresponds to equality.

Yeah, okay, no worries.

There are even more of them. And symbols can be used to mean different things. ≡ can be used for identity, equivalence relation or some other things. And partial equivalance relation if is often denoted with ≈.

Yet both can be denoted with = (depending on what kind of math you are discussing) and, more, there may be more than one equality on one math article!

When that happens addition equality marks are used: `≑`, `≔`, `≕`, `≘`, `≙`, `≚`, `≛`, `≜`, `≣`, `⊜` and so on.

Yeah, I have seen ≈ for that too.

Anyway, my point is: an equivalence relation isn't necessarily corresponding to equality. And the Rust docs are messy on that matter.

I don't think that the phrases "partial equality" or "total equality" are well-established mathematical terms.

`PartialEq` describes a partial equivalence relation. And `Eq` either describes a total equivalence relation (which is reflexive) or equality (which is also reflexive). It's been debated in the previously mentioned PR #103046 whether `Eq` rather describes (or should describe) a total/reflexive equivalence relation or actual equality.

Frankly if I would see discussion like that about some math paper I would just go and ask: Why haven't you wrote something unambigious like the following:

1. `a == b``partial_cmp(a, b) == Some(Equal)`.
2. `a < b``partial_cmp(a, b) == Some(Less)`
3. `a > b``partial_cmp(a, b) == Some(Greater)`
4. `a <= b``a < b``a == b`
5. `a >= b``a > b``a == b`
6. `a != b` ⇔ ¬ `(a == b)`.

Oh, you did? Then what's the point of arguing about terms if we have all the properties in form of unambigious maths formulas?

For example, `<=` doesn't (always) correspond to partial orders, even though the implementation of this operator is defined by the `PartialOrd` trait.

Demonstration:

``````fn main() {
let a = f64::NAN;
// if `<=` described a (non-strict) partial order,
// then `a <= a` would need to be true:
assert!(a <= a); // but it is not
}
``````

I think the main motive for my original question was to not go into details of PartialEq/PartialOrd theory, but was rather more practical (apologies for not stating it more clearly upfront):

For the `Person` struct that I used in the example, how should I define the `Eq` and `Ord` traits such that this struct can be easily and correctly used in Rust standard containers and algorithms?

For instance, I want to

1. Use `sort()` method to sort `Person`s by age => expectation is to sort `Person` by their age only.
2. Use `Person` as a key in `BtreeMap` and `HashMap` => expectation is to uniquely identify each `Person` with a given name.

Is it correct to deduce from the above discussion, that this cannot be achieved using the Ord/Eq traits on the `Person` struct?

Yes, I see the point here.

I think what still bothers me is that `<`, `<=`, `>=`, and `>` operators come from `PartialOrd` trait whereas `==` comes from `PartialEq` trait; even though `PartialOrd` trait allows for `Ordering::Equal` to be returned.

I do not understand all of these well enough to make a suggestion, but it seems that for structs that implement `PartialOrd` trait, it is redundant (and confusing) to further implement `PartialEq` trait.

It's another way round, actually - it's possible to implement `PartialEq` while not implementing `PartialOrd`.