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");
    }
}

(Playground)


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]


  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"? :man_shrugging: (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?

Because it can confuse people and lead to contradictions.

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
}

(Playground)

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 Persons 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.