Implementing Ord for a type is awkward?

Question

I have a newtype and I want to implement Ord:

use std::cmp::{Ord, Ordering};

struct MyType(isize);

impl Ord for MyType {
    fn cmp(&self, &other: Self) -> Ordering {
        let MyType(ref lhs) = *self;
        let MyType(ref rhs) = *other;
        lhs.cmp(rhs)
    }
}

When I try to compare two variables of my types, I get errors:

error[E0277]: the trait bound `MyType: std::cmp::PartialOrd` is not satisfied
 --> src/main.rs:5:6
  |
5 | impl Ord for MyType {
  |      ^^^ can't compare `MyType` with `MyType`
  |
  = help: the trait `std::cmp::PartialOrd` is not implemented for `MyType`

error[E0277]: the trait bound `MyType: std::cmp::Eq` is not satisfied
 --> src/main.rs:5:6
  |
5 | impl Ord for MyType {
  |      ^^^ the trait `std::cmp::Eq` is not implemented for `MyType`

When I implement PartialEq, Eq and PartialOrd (gt(), lt(), eq(), ge(), le(), etc.), everything works fine, but if I provided cmp, we can infer functions like lt() and eq()! This is redundant! I don't like this!

When looking in the docs, I see this in the definition of Ord:

pub trait Ord: Eq + PartialOrd<Self> 

This looks like the trait inherits from Eq and PartialOrd. Why can't the trait provide default implementations for the required methods from the inherited traits using the cmp function? I don't know how inheritance of traits works and searching turned up nothing useful, but I think this is something that should be possible.

How is this done in Rust? I hope not this way...

Answer 1

Please consider this as an addendum to the original answers, which are suited for your specific case. This answer deals with the second part of your question.

Consider this struct:

struct Person {
    id: u32,
    name: String,
    height: u32,
}

Equality: the PartialEq and Eq traits

PartialEq Trait, From the docs

Trait for equality comparisons which are partial equivalence 
relations. This trait allows for partial equality, for types that do not
have a full equivalence relation. For example, in floating point numbers
NaN != NaN, so floating point types implement PartialEq but not Eq.

Formally, the equality must be (for all a, b and c):

symmetric: a == b implies b == a; and
transitive: a == b and b == c implies a == c.

So if you want to express what it means for values of your types to be equal, you must implement the PartialEq trait. Implementing it allows us to write x == y and x != y for our types.

impl PartialEq for Person {
    fn eq(&self, other: &Person) -> bool {
        self.height == other.height
    }
}

Note that we are deciding the equality of Person struct just on the basis of the heights. You could also have implemented this eq method if you want to compare every struct field:

fn eq(&self, other: &Person) -> bool {
     self.id == other.id && self.name == other.name && self.height == other.height
}

But it would be easier to simply add #[derive(PartialEq)] if that's the behavior you want.

Eq Trait, From the Docs

Trait for equality comparisons which are equivalence relations.

This means, that in addition to a == b and a != b being strict inverses, 
the equality must be (for all a, b and c):

reflexive: a == a;
symmetric: a == b implies b == a; and
transitive: a == b and b == c implies a == c.

This property cannot be checked by the compiler, and therefore Eq implies
PartialEq, and has no extra methods.

Derivable
This trait can be used with #[derive]. When derived, because Eq has no extra methods, 
it is only informing the compiler that this is an equivalence relation rather than a 
partial equivalence relation. Note that the derive strategy requires all 
fields are Eq, which isn't always desired.

PartialEq is for relations which are not necessarily reflexive (i.e. there can be such x that x != x) and that Eq is a marker trait which says that relation is also reflexive (and now it is a proper equivalence relation).

You can also implement the Eq trait manually with an empty impl block

impl Eq for Person {}

But, again, it’s easier to add Eq to your #[derive(Eq)] list.

Ordering: the PartialOrd and Ord traits

The relative ordering of values is calculated using the operators <, <=, >= and >. To implement these for your own types, you must implement the PartialOrd trait.

Before you can implement PartialOrd, you must implement PartialEq.

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

Ordering is an enum with these values:

pub enum Ordering {
    Less,
    Equal,
    Greater,
}

partial_cmp returns an Option and not an Ordering because there are types of which values cannot always be compared, such as floating-point numbers. NaNs are not representable numbers; expressions such as 3.0 < NaN don’t make any sense. In those cases, partial_cmp returns None. Floating-point values are the only case in the standard library where this happens. More can be found here.

The fact that partial_cmp returns an Option<Ordering> has a consequence: it might not be possible to place two values, x and y, into a definite order. In practice, this means that implementing PartialOrd is not sufficient to make your values sortable. You also need to implement the Ord trait.

Before you can implement Ord, you must first implement PartialOrd, Eq and PartialEq.

For our Person struct, again we can delegate down to one of our member variables:

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

Answer 2

For your specific case I'd use #[derive]:

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct MyType(isize);

fn main() {
    let a = MyType(5);
    let b = MyType(6);

    println!("{:?}", a.cmp(&b))
}

If you need to special case your Ord implementation, you still have to write out that code, there's nothing that can save us there! You can still derive implementations for the other traits, if it makes sense to do so.

The other part of your question is ambiguous, so I'll answer it both ways I read it:

Why can't Ord be automatically provided by anything with PartialOrd?

Let's look at the docs for PartialOrd and Ord.

PartialOrd says: "The comparison must satisfy antisymmetry and transitivity", while Ord says: "types that form a total order". These are math terms and I won't do as good a job as Wikipedia will at describing them.

However, we can use floating point numbers as an example. Floats have a special value called NaN. Comparing against this value is tricky. For example, all of 1.0 < NaN, 1.0 == NaN and 1.0 > NaN are false! These don't form a total order, but we can still compare one value against another. This is why PartialOrd exists - to allow us to compare types like this. incidentally, PartialEq exists for similar reasons.

We can't define Ord in terms of PartialOrd because we don't have the appropriate guarantees about the underlying types. This is Rust's type system saving us from making a mistake!

Why can't PartialOrd be automatically provided by anything with Ord?

The problem here is that more types are PartialOrd than they are Ord. If we required everything to be Ord, then we couldn't have any floating point comparisons, because they don't have a total order, or we'd have to give up on having a total order and losing out on the safety that it provides.

However, there have been ideas to automatically do this for derive. Proposed RFC 2385 would allow the above code to be reduced to:

#[derive(Debug, Copy, Eq, Ord)]
struct MyType(isize);

when I implement PartialOrd (gt(), lt(), eq(), ge(), le() ...)

Note that PartialOrd does have default implementations, you only need to implement partial_cmp. The others are there for ease-of-use or possibly performance reasons.