Pre-RFC: std::cmp::WellOrdering

[mightyiam]

In implementing a bookkeeping crate, I have found that a property of moves (could be called transactions) in an account is that each move results in a new balance in that account. Thus, it seems that moves in an account are not just ordered, but well-ordered. This means that [std::cmp::Ordering](https://doc.rust-lang.org/std/cmp/enum.Ordering.html) is insufficient, because it includes an Equal variant.

Would it make sense to have an std::cmp::WellOrdering enum that includes only Less and Greater?

[CAD97]

You still have the identity case, x.cmp(x), which would compare equal. If I understand well ordering, all Ord finite types are well ordered. E.g. the number set 0..=255u8 is well ordered, but 0u8.cmp(0u8) is still equal.

Even if all of your type instances compare differently, you can always compare a value to itself.

[mightyiam]

@CAD97

Even if all of your type instances compare differently, you can always compare a value to itself.

In a well-ordered set of u8, the same instance cannot appear more than once, as I understand it. So in a sorting algorithm, a number would not compare with itself?

[scottmcm]

@mightyiam

In a well-ordered set of u8 , the same instance cannot appear more than once, as I understand it.

The problem I see here is that Ord::cmp takes references, not owned instances. So even if you can't have two different instances that compare the same, you still have compare(&x, &x).

(And you don't want comparisons to take ownership of the things, because then you can't do anything with them after comparing.)

[pcpthm]

You seem to misunderstand what is a well-ordering in the mathematical sense. It is a special kind of a total ordering.

It doesn't make sense to have WellOrdering like Ordering because the well ordering is a property of an ordering (the Ord trait), not a particular comparison result (an Ordering value).

And not all total order is a well-order. For example, the usual ordering of the integers isn't a well ordering because we have an infinite descending chain 0 > -1 > -2 > ....

[joegomain]

@mightyiam

In a well-ordered set of u8 , the same instance cannot appear more than once, as I understand it. So in a sorting algorithm, a number would not compare with itself?

Items of a set, say of the set of u8s, are the individual values. Not the instances at runtime. Two instances of the number 8 are the same value. They are both the same item of the set. It does not make sense to say "the same instance cannot appear more than once". Appear where? In memory? at run time?

Had we a marker trait

trait Unique: PartialEq {
}

Which has a rule such that for any a: T and b: T where T: Unique we can assert_ne!(a, b). That is any two instances of T are guaranteed to not equal, i.e. not be the same value. Only then, we could have a trait

trait WellOrd: Unique + Ord {
    fn well_cmp(l: Self, r: Self) -> WellOrdering {
        match l.cmp(r) {
            Odering::Less => WellOdering::Less,
            // because Unique gurantees unequalness
            _ => WellOrdering::Greater,
        }
}

enum WellOrdering {
    Less,
    Greater,
}

As with any marker traits, rules are only rules that implementers are expected to abide to.

Problem is that it is impossible to implement Ord. As @CAD97 has mentioned, what would the expression x.cmp(x) evaluate to? we know x == x is false so it's not Equal and there is no decisive way to pick one of Less or Greater.

[mightyiam]

@joegomain

Items of a set, say of the set of u8 s, are the individual values. Not the instances at runtime.

Yes, forgive me. I did mean values.

You claim that only a type that implements Unique (no two instances are equal) could implement WellOrd. That seems reasonable, because the method that is proposed for implementing WellOrd is

fn cmp(&self, other: &Self) -> WellOrdering

Yet, this function does not seem appropriate for WellOrd. It seems that WellOrd is not a trait of a primitive type but of a collection. It means to convey that the collection is well-ordered. It would require that the values of the collection are unique. A collection of unique values is a set, right? So, a set of T: Ord is a well-ordered set. Is this right?

[mbrubeck]

@mightyiam

So, a set of T: Ord is a well-ordered set. Is this right?

Yes, as long as the set is finite: In a finite set, every total order is a well order.

The difference between total order and well order matters only in infinite sets. There is no such distinction for collections like BTreeSet, which are necessarily finite because they store their elements in memory. Therefore, the Ord trait for total ordering is sufficient for such collections.

[jan_hudec]

@mightyiam

A collection of unique values is a set, right? So, a set of T: Ord is a well-ordered set. Is this right?

A HashSet or a BTreeSet of T: Ord yes, a set in mathematical sense, no.

The difference is that in a total order elements may be equivalent that are not the same element, and in a set in mathematical sense, these are not excluded. For example you can define comparison on ℕ by ⎣n/10⎦ and it is still a total order, but it is not a well order, because all the number 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 are equal under it and so there is no least element.

But since HashSet and BTreeSet use the ordering to determine if they already contain the element, so they can't contain multiple equivalent elements, so the ordering of their elements is always a well ordering.

[steffahn]

@jan_hudec

For example you can define comparison on ℕ by ⎣n/10⎦ and it is still a total order, but it is not a well order

Not correct. This will be neither a well-order nor a total order because it’s lacking:

Antisymmetry

If 𝑎 ≤ 𝑏 and 𝑏 ≤ 𝑎 then 𝑎 = 𝑏;

It is a total preorder ^{[and here’s another link]} though.

[mightyiam]

In my implementation, I ended up giving up on the idea of the user providing something that implements a trait for me to order their moves by. I put the responsibility of ordering on the user of the API. They have access to existing moves and their indexes and therefore can decide where to insert the next move by index.

[nakacristo]

IMHO, in that situation is good enough to use Ord bounds to be provided from Vec::sort and similar and to state in the API that it will only work correctly if the Ord implementation satisfy the additional criteria.

Note how the Ord documentation state: "Implementations of PartialEq , PartialOrd , and Ord must agree with each other." That is, some user can implement those traits without respecting the documented contract. And then sorting and insertion into some collection will have have strange behaviors. I recommend you to proceed similarly, by just documenting the hard-to-automate parts. I do not know if there is some standard approach towards bad implementors of these traits. I would default to assume they are all good unless there is something critical, situation where it could be worth some execution-time checking.

[CAD97]

@nakacristo

I do not know if there is some standard approach towards bad implementors of these traits. I would default to assume they are all good unless there is something critical, situation where it could be worth some execution-time checking.

Standard procedure (for safe traits such as Ord) is that incorrect implementations are assumed correct, and may cause arbitrarily bad logic bugs if incorrect, but implementations may not rely on their correctness to validate unsafe code (and thus a bad impl may not cause memory unsafety).

Still, you'd be looked at funny if you bailed out and stole bank account info if someone provided a bad Ord impl, though that's still safe. You'll never be blamed if it leads to something reasonably resulting from arbitrarily out-of-order elements.

[mightyiam]

Regarding bounding on Ord: a naive user implementation could be some type that orders the moves by date-time, missing the fact that occasionally, even date-time could end up equal. In bookkeeping, this would result in an account balance being the same at two different moves. I imagine this to be a critical bug in the bookkeeping domain and so I don't like being the author who allowed this. Therefore my API requires insertion of moves by index. Nothing can go wrong there other than an out of bounds panic that is easy to uphold.