# Pre-RFC: std::cmp::WellOrdering

**URL:** <https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494>\
**Category:** libs\
**Created:** [December 2, 2020, 3:53am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494 "2020-12-02T03:53:22Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![mightyiam](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mightyiam/32/7306_2.png) [@mightyiam](https://internals.rust-lang.org/u/mightyiam)\
**Post date:** [December 2, 2020, 3:53am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/1 "2020-12-02T03:53:22Z")

</div>

In implementing a [bookkeeping crate](https://crates.io/crates/bookkeeping), 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](https://en.wikipedia.org/wiki/Well-order). 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`?

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [December 2, 2020, 4:25am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/2 "2020-12-02T04:25:26Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mightyiam](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mightyiam/32/7306_2.png) [@mightyiam](https://internals.rust-lang.org/u/mightyiam)\
**Post date:** [December 2, 2020, 4:46am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/3 "2020-12-02T04:46:08Z")

</div>

> [@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?

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [December 2, 2020, 5:16am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/4 "2020-12-02T05:16:21Z")

</div>

> [@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.)

---

<div class="post-metadata">

**Author:** ![pcpthm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pcpthm/32/4952_2.png) [@pcpthm](https://internals.rust-lang.org/u/pcpthm)\
**Post date:** [December 2, 2020, 5:49am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/5 "2020-12-02T05:49:19Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![joegomain](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/joegomain/32/7253_2.png) [@joegomain](https://internals.rust-lang.org/u/joegomain)\
**Post date:** [December 2, 2020, 7:27pm UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/6 "2020-12-02T19:27:31Z")

</div>

> [@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 `u8`s, 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

```rust
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

```rust
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`.

---

<div class="post-metadata">

**Author:** ![mightyiam](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mightyiam/32/7306_2.png) [@mightyiam](https://internals.rust-lang.org/u/mightyiam)\
**Post date:** [December 3, 2020, 6:18am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/7 "2020-12-03T06:18:22Z")

</div>

> [@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

```rust
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?

---

<div class="post-metadata">

**Author:** ![mbrubeck](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mbrubeck/32/174_2.png) [@mbrubeck](https://internals.rust-lang.org/u/mbrubeck)\
**Post date:** [December 3, 2020, 6:46am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/8 "2020-12-03T06:46:08Z")

</div>

> [@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.

---

<div class="post-metadata">

**Author:** ![jan\_hudec](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jan_hudec/32/4100_2.png) [@jan\_hudec](https://internals.rust-lang.org/u/jan_hudec)\
**Post date:** [December 7, 2020, 9:42am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/9 "2020-12-07T09:42:43Z")

</div>

> [@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.

---

<div class="post-metadata">

**Author:** ![steffahn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steffahn/32/13288_2.png) [@steffahn](https://internals.rust-lang.org/u/steffahn)\
**Post date:** [December 7, 2020, 10:57am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/10 "2020-12-07T10:57:06Z")

</div>

> [@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](https://en.wikipedia.org/wiki/Well-order) nor a [total order](https://en.wikipedia.org/wiki/Total_order) because it’s lacking:

> ### [Antisymmetry](https://en.wikipedia.org/wiki/Antisymmetric_relation)
> 
> If 𝑎 ≤ 𝑏 and 𝑏 ≤ 𝑎 then 𝑎 = 𝑏;

It is a total [preorder](https://en.wikipedia.org/wiki/Preorder) [and here’s [another link](https://en.wikipedia.org/wiki/Weak_ordering#Total_preorders)] though.

---

<div class="post-metadata">

**Author:** ![mightyiam](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mightyiam/32/7306_2.png) [@mightyiam](https://internals.rust-lang.org/u/mightyiam)\
**Post date:** [December 7, 2020, 11:05am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/11 "2020-12-07T11:05:41Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![nakacristo](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nakacristo/32/10249_2.png) [@nakacristo](https://internals.rust-lang.org/u/nakacristo)\
**Post date:** [December 7, 2020, 4:25pm UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/12 "2020-12-07T16:25:02Z")

</div>

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`](https://doc.rust-lang.org/std/cmp/trait.PartialEq.html), [`PartialOrd`](https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html), 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.

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [December 7, 2020, 7:14pm UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/13 "2020-12-07T19:14:24Z")

</div>

> [@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.

---

<div class="post-metadata">

**Author:** ![mightyiam](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mightyiam/32/7306_2.png) [@mightyiam](https://internals.rust-lang.org/u/mightyiam)\
**Post date:** [December 8, 2020, 3:38am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/14 "2020-12-08T03:38:03Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [March 8, 2021, 3:38am UTC](https://internals.rust-lang.org/t/pre-rfc-std-wellordering/13494/15 "2021-03-08T03:38:09Z")

</div>

Closed on March 8, 2021, 3:38am UTC

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.
