Rfcs: Ordering::and_then

[digama0]

From https://github.com/rust-lang/rust/issues/34774:

This seems like an obvious and missing function from std::cmp::Ordering:

impl Ordering {
    pub fn then(self, other: Ordering) -> Ordering {
        match self {
            Ordering::Equal => other,
            o => o,
        }
    }

    pub fn and_then<F: FnOnce() -> Ordering>(self, other: F) -> Ordering {
        match self {
            Ordering::Equal => other(),
            o => o,
        }
    }
}

This is useful for creating comparators which do lexicographic order. The second variant allows for skipping the order calculation if it is not necessary.

To explain the name then / and_then: Java has a similar function for comparators, called thenComparing. The idea is that you can read a comparison function like

self.name.cmp(other.name).then(self.address.cmp(other.address))

as "compare by name, then by address". The then / and_then difference with a closure is inspired by Rust's function names for Option like or (by value) / or_else (by closure).

[ExpHP]

Bikeshed: To me or_else actually feels more to me like the proper name for this, as it short circuits once it reaches some sort of non-neutral value. (Equal playing a role similar to None or false)

[digama0]

@ExpHP To add to the similarity, this is also the behavior of javascript's || operator - it returns the first truthy value, which would act like this function if the values are represented as -1, 0, 1. I am not attached to any particular name.

[rednum]

Is there any update on this? I'd also like to have this feature, can I contribute somehow?

@digama0 This would also be similar to Haskell's monoid instance for Data.Ord.Ordering.

[digama0]

@rednum I like that, that's a clever use of monads. (I assume you meant _monad_ not _monoid_ which is a very different algebraic structure.)

[sfackler]

@rednum These seem like reasonable APIs that match conventions, so it should be fine to just add them (marked unstable) and open a PR against rust-lang/rust!

[rednum]

@digama0
I've meant monoid, see:
https://hackage.haskell.org/package/base-4.9.0.0/docs/src/GHC.Base.html#line-302
so the example in original post would look something like this in Haskell:

myComparator self other = 
    (name self `compare` name other) `mappend` 
    (address self `compare` address other)

@sfackler
I also thought that something like this could be useful, thoughts?

impl Ordering {
    pub fn then_cmp(self, o1: &Ord, o2: &Ord) -> Ordering {
        match self {
            Ordering::Equal => o1.cmp(o2),
            o => o,
        }
    }

so that you could write

self.name.cmp(other.name).then_cmp(self.address, other.address)

[abonander]

@rednum That's functionally equivalent to and_then() but less flexible:

self.name.cmp(other.name).and_then(|| self.address.cmp(other.address))

[sfackler]

That could be convenient, yeah, though I'd personally lean towards just and and and_then for now to match with Option &co.

[bluss]

and seems better than or, since the latter mismatches. Compare to an expression like a == b || c <= d where the second comparison is done when a and b are not equal.

Why not just use chain as the name? The conjunctions really have to fit perfectly, otherwise I wouldn't use them.

[rednum]

I think chain is better than and/or. How about the variant that takes function? I put it for consistency with Option, but I don't think it's really necessary, and neither chain_then or chain_fn sound convincing to me.

[clarfonthey]

This function is a bit awkward to use in implementations of PartialOrd.

For example, let's take a simple tuple for Ord:

fn cmp((t11, t12): (usize, usize), (t21, t22): (usize, usize)) -> Ordering {
   t11.cmp(t21).then_with(|| t12.cmp(t22))
}

That's pretty simple, but:

fn partial_cmp((t11, t12): (f64, f64), (t21, t22): (f64, f64)) -> Option<Ordering> {
   t11.partial_cmp(t21).and_then(|c1| {
        if let Some(c2) = t12.partial_cmp(t22) {
            c1.then(c2)
        }
    })
}

Note that you can't easily do a then_with for partial_cmp. Either that or I can't figure it out.

Perhaps there should be a version of these functions that works with Option<Ordering>?

[bluss]

@clarcharr I guess it needs to be something else than usize to be relevant, something that doesn't impl Ord, you mean? Almost seems like a job for try_opt!() I think.

[clarfonthey]

@bluss I used usize because I was a bit lazy with the syntax, but I just substituted usize for f64 in my example. ;)

Perhaps try_opt! would work but it still seems appropriate to have the parallels between Ordering and Option<Ordering>.

[ExpHP]

Hmm, even with try_opt! I can't quite figure how it could be done.

fn partial_cmp((a1, a2): (f64, f64), (b1, b2): (f64, f64)) -> Option<Ordering> {
    let c = try_some!(a1.partial_cmp(b1));
    let c = c.or_else(|| try_some!(a2.partial_cmp(b2))); // <-- whoops, returns None in the closure!
    Some(c)
}

[ExpHP]

Perhaps try_opt! would work but it still seems appropriate to have one for Option so that PartialOrd implementations are easier.

On this I fear there may be multiple reasonable definitions of (Option<Ordering>, Option<Ordering>) -> Option<Ordering>. I will confess none immediately came to mind when I first read the above post, and I had to figure it out from your implementation.

As an example of another definition: rednum mentioned above that in Haskell, Ordering exposes functionality like this through Monoid operator (mappend). As it turns out, Maybe Ordering is a Monoid too, but its composition is more like this:

                         Second argument
       mappend | Nothing  Just EQ  Just LT  Just GT
       --------+-----------------------------------
       Nothing | Nothing  Just EQ  Just LT  Just GT
First  Just EQ | Just EQ  Just EQ  Just LT  Just GT
 arg   Just LT | Just LT  Just LT  Just LT  Just LT
       Just GT | Just GT  Just GT  Just GT  Just GT

So None here plays a neutral role similar role to Some<Equal>.

[clarfonthey]

@ExpHP although Haskell does this, this isn't how Rust does it.

For example, take this code: https://is.gd/G2TNGV

use std::f64::NAN;

fn main() {
    println!("{:?}", (NAN,).partial_cmp(&(NAN,)));
    println!("{:?}", (NAN,).partial_cmp(&(0.,)));
    println!("{:?}", (NAN, NAN).partial_cmp(&(NAN, NAN)));
    println!("{:?}", (NAN, NAN).partial_cmp(&(NAN, 0.)));
    println!("{:?}", (NAN, 0.).partial_cmp(&(NAN, 0.)));
}

Prints None for every line. Which means that that interpretation, although being what Haskell does, is not what Rust does.

Which makes sense IMHO to be the only accepted interpretation, but there could be arguments in the other direction.

[ExpHP]

Ah, I see now, there is indeed a definition which is already very-well established in existing PartialOrd definitions in Rust, both for built-in types as well as via #[derive(PartialOrd)]. Not only that but it's very tricky to get right without an explicit match statement!

With small modifications to your implementation above to get it to compile: (the most significant difference being the addition of an else { None } branch):

fn posted_partial_cmp((t11, t12): (f64, f64), (t21, t22): (f64, f64)) -> Option<Ordering> {
   t11.partial_cmp(&t21).and_then(|c1| {
        if let Some(c2) = t12.partial_cmp(&t22) {
            Some(then(c1, c2))
        } else { None }
    })
}

its output actually differs subtly from the standard implementation (see https://is.gd/rM8cSN) in cases where the second comparison fails, and I see no easy/composable fix (tables are arranged as in my prior post):

tuple PartialOrd
  None           None           None           None         
  None           Some(Equal)    Some(Less)     Some(Greater)
  Some(Less)     Some(Less)     Some(Less)     Some(Less)   
  Some(Greater)  Some(Greater)  Some(Greater)  Some(Greater)

posted implementation (with alterations)
  None           None           None           None         
  None*          Some(Equal)    Some(Less)     Some(Greater)
  None*          Some(Less)     Some(Less)     Some(Less)   
  None*          Some(Greater)  Some(Greater)  Some(Greater)

*note: Changing the else { None } to else { c1 } changes these
   three elements to Some(Equal) Some(Less) Some(Greater)

Meanwhile, it is apparent that much like Ordering::then, the correct behavior is very easily described by a simple match statement which could be easily provided in helper functions:

impl Option<Ordering> {
    // modulo heavy bikeshedding
    pub fn and_then_partial<F>(self, other: F) -> Option<Ordering>
    where F: FnOnce() -> Option<Ordering> {
        match self {
            Some(Ordering::Equal) => other(),
            c => c,
        }
    }

    pub fn then_partial(self, other: Option<Ordering>) -> Option<Ordering> {
        match self {
            Some(Ordering::Equal) => other,
            c => c,
        }
    }
}

I wholeheartedly agree that functions that represent this well-established convention for PartialOrd ought to exist somewhere in the standard library, in addition to the proposed functions for Ordering!

[clarfonthey]

Sounds good to me! I would probably name them partial_then and partial_then_with just for consistency, but that's a very nice implementation.

[clarfonthey]

One other quick note on the way I conceptualised this: None from PartialOrd basically says that you can't compare the two items. So, I would consider None to propagate across multiple fields; if you can't compare one field, then the entire object is incomparable. This shows when you add a NaN into the mix, because NaN isn't comparable.

The monoid version from Haskell makes sense within the way I understand Maybe, but for actual comparables I understand why (NaN, 0) < (NaN, 1) returns 1, but should (NaN, 0) < (-NaN, 1) still return true? It seems like you'd have to break the invariant of being able to split the comparisons field by field, and I don't really like that interpretation. I'd be more open to understanding the other ones, though!

[ExpHP]

I think the current choice makes sense in the context of lexicographic comparison, which is how <Vec as PartialOrd> and Iterator::partial_cmp work. Since they have to deal with iterables of different length, there is already the notion of having a defined order despite uncomparable fields.

One should also consider the behavior for infinite iterators. If Iterator::partial_cmp always returned None when at least one field is incomparable, then partial_cmp on two infinite iterators would only ever be capable of returning None! (If you compared two infinite iterables of integers, it would never return.) Contrast this with the current behavior, which is that a comparison of two infinite iterables will never return if and only if they are equal.

Some might consider the current behavior a footgun, but it really depends on the application; the current behavior is in line with existing (and unavoidable) behavior on Iterator::cmp, and I've found comparisons between infinite iterators to be useful in mathematical contexts where the iterators are provably not equal.

---

A similar argument is that the current definition permits local reasoning; one can say that (0., x) < (1., y) for all possible x and y. Or indeed, one can even say that

(0., x0, x1, ...xN) < (1., y0, y1, ...yM)  forall N, M, {xi}, {yi}

[mbrubeck]

These were added as then and then_with by rust-lang/rust#37054.

[ExpHP]

Just as a peculiar data point on the name, when I saw my first comment here again today, I couldn't believe that I had suggested or! Instead, my viewpoint this time was more aligned with @bluss in that I would regard the case where two values are equal as a successful comparison—making and the more natural choice.

I think that at the time I wrote that post, I was primarily coding in Haskell, so the first thought that popped into my head was probably how I might implement that using the Alternative instance for Maybe (guess what that does). In contrast, my view coming in today has been colored by lots of shell scripting, where success is neutral.

Best to just stay away from the names "and" and "or" entirely.