Cats Order needs an orElseBy combinator

[benhutchison]

Leaving aside the question of whether cats.Order existing (on top of scala.math.Ordering on top of java.util.Comparator) was wise decision 🙄 , at least it ought to be greaterThanOrEqual to its predecessor.

But alas, it lacks something valuable that Ordering has; a convenient syntax to construct a n-level hierarchical ordering for a record, by delegating to the orderings of several record fields. For example, if we have a case class Person(name: String, age: Int) we might wish to order by age but if ages are equal, use name as a discriminator. This is super common IME. Eg SQL has built in syntax for it order by age, name.

There are at least two attempts at addressing this in cats.Order, but alas both are less convenient than the (pre-existing) combinator in scala.math.Ordering:

def orElseBy[S](f: T => S)(implicit ord: Ordering[S]): Ordering[T]

Hence we find code like this in the wild:

      given Order[Single] = Order.fromOrdering(
      Ordering
        .by[Single, VPNTier](_.tier)
        .orElseBy(it => (it.lang1, it.lang2))
        .orElseBy(_.num)
        .orElseBy(_.postfix)
    )

The attempts in cats.Order are:

• code. Order.whenEqual[Person](Order.by(_.age), Order.by(_.name)). Well it's already looking slightly awkward, but what if we wanted to add a 3rd discriminator? We'd need to nest it inside the second arg with another call to Order.whenEqual. Confusing right nesting.
• code. The whenEqual Monoid is beautiful and tantalizes us with the promise of val o: Order[Person] = Order.by(_.age) |+| Order.by(_.name). But I could not get the types to infer properly even on Scala 3.5 RC1.

If it ain't broke, don't fix it. orElseBy does the job well and should be brought into Cats.

[johnynek]

Seems like a good PR.

I don't know all the motivations for Order but I think it was that Ordering I believe was contravariant and scala had (or maybe has?) some issues with very surprising implicit resolution on contravariant type classes.

[satorg]

I think it would be a great addition indeed.

However, I wonder why orElse and orElseBy were added to Ordering, but not PartialOrdering.
And whether we'd like to address it in PartialOrder instead.

[benhutchison]

I wonder why orElse and orElseBy were added to Ordering, but not PartialOrdering

What would be the semantics of orElse etc when two elements are not comparable on the primary PartialOrder? ie tryCompare returns None. presumably theres no delegation for consistency. The name orElse could lead people to think it tries another PO if the first is incomparable.

That semantic does seem workable . Perhaps the slight ambiguity, or simply that PartialOrdering is less commonly used, is the reason.

[satorg]

That's right. So I think that in theory, PartialOrder could offer two different orElse like combinators, e.g. orElseOnEqual and orElseOnUnrelated. Then in Order the former one should be simply inherited without changes, while the latter could short-circuit in order to simply return a result of "this" Order instance.

Not sure if all that makes sense though, wdyt?

[benhutchison]

A precedent for Partial order orElse combinator

That's right. So I think that in theory, PartialOrder could offer two different orElse like combinators, e.g. orElseOnEqual and orElseOnUnrelated

I'm reluctant to implement a orElseOnUnrelated combinator without a clear use case.

Then in Order the former one should be simply inherited without changes

In spirit, yes. But partial orders return a comparison wrapped in an Option, while total orders omit the Option.

Interestingly, ZIO nicely avoids an Option by using a 4-branch sealed trait (LT, Eq, GT, Incomparable), which nests a 3-branch trait used for total orders 🆒

[satorg]

In spirit, yes. But partial orders return a comparison wrapped in an Option, while total orders omit the Option.

Interestingly, ZIO nicely avoids an Option by using a 4-branch sealed trait (LT, Eq, GT, Incomparable), which nests a 3-branch trait used for total orders 🆒

Actually, in Cats the tryCompare method (which returns Option) is complementary. The primary one is partialCompare:

cats/kernel/src/main/scala/cats/kernel/PartialOrder.scala

Lines 59 to 80 in dd89133

	def partialCompare(x: A, y: A): Double
	/**
	* Like `partialCompare`, but returns a [[cats.kernel.Comparison]] instead of an Double.
	* Has the benefit of being able to pattern match on, but not as performant.
	*/
	def partialComparison(x: A, y: A): Option[Comparison] =
	Comparison.fromDouble(partialCompare(x, y))
	/**
	* Result of comparing `x` with `y`. Returns None if operands are
	* not comparable. If operands are comparable, returns Some[Int]
	* where the Int sign is:
	*
	* - negative iff `x < y`
	* - zero iff `x = y`
	* - positive iff `x > y`
	*/
	def tryCompare(x: A, y: A): Option[Int] = {
	val c = partialCompare(x, y).sign
	if (isNaN(c)) None else Some(c.toInt)
	}

So it still should be quite efficient.

[satorg]

I'm reluctant to implement a orElseOnUnrelated combinator without a clear use case.

Agree. I'm just trying to poke around different possibilities and outcomes. For example, if a method can be added to a base trait, it is usually better to add it there from the beginning even if it is not needed right away. Because if we decided to add it to the base class later, then it would be more difficult to overcome inevitable binary compatibility issues.

But when it comes to orElseOnUnrelated, it does not seem to be the case anyway – looks like it can be added later if necessary without any consequences (unless I'm missing something).

[morgen-peschke]

What would be the semantics of orElse etc when two elements are not comparable on the primary PartialOrder? ie tryCompare returns None. presumably theres no delegation for consistency. The name orElse could lead people to think it tries another PO if the first is incomparable.

A possible fix for this provides a nice parallel with the existing method: name it whenEqual and expose it on the instance rather than the companion object.

This seems to imply fallbacks in any ambiguous case (equal or incomparable):

PartialOrdering
  .by[Single, VPNTier](_.tier)
  .orElseBy(it => (it.lang1, it.lang2))
  .orElseBy(_.num)
  .orElseBy(_.postfix)

This doesn't have that connotation (at least to my reading):

PartialOrdering
  .by[Single, VPNTier](_.tier)
  .whenEqual(it => (it.lang1, it.lang2))
  .whenEqual(_.num)
  .whenEqual(_.postfix)