Scala idiom for ordering by multiple criteria

问题:

I want to do something like this:

class Foo extends Ordered[Foo] {
   val x
   val y
   val z
   .
   .
   .
   .
   def compare(that: Foo) = {
      val c0 = this.length compareTo that.length          // primary comparison
      lazy val c1 = this.x compareTo that.x               // secondary comparison
      lazy val c2 = this.y.size compareTo that.y.size     // tertiary comparison
      lazy val c3 = this.z.head compareTo that.z.head     // final tie breaker
      if (c0 != 0) c0 else if (c1 != 0) c1 else if (c2 != 0) c2 else if (c3 != 0) c3 else c4
   }    
}

I was wondering if there was any cleaner way to write this kind of thing. I am expecting some thing like Ordering.multipleBy(ordering: Ordered[A]*) signature which takes a varargs of comparables and selects first non zero.

回答1:

It is often better to use Ordering instead of Ordered. Ordering is a type class and is much more flexible than Ordered (if only because Ordered must be implemented by the type to compare, while with Ordering you can define this outside). To define the natural ordering (default Ordering instance) for your type, you just define an implicit ordering value in the companion object.

So, enough with the preamble. The nice thing is that when using Ordering what you want to do is pretty simple, as there is an implicit ordering for tuples (provided that the tuple elements themselves have a orderings)`:

object Foo {
  implicit val FooOrdering = Ordering.by{ foo: Foo => 
    (foo.length, foo.x, foo.y, foo.z) 
  }
}

In addition, there is an implicit conversion that converts any value that has an Ordering type class instance into an Ordered value (see Ordered.orderingToOrdered) so we have nothing special to do to automagically being able to pass any instance of Foo to a function that expects an Ordered[Foo])

---

UPDATE: Concerning your new question:

Slightly related - is there any way to compose orderings?

One way to do it would be to use mostly the same technic based on Ordering.by and conversion to tuples, but explicitly passing the orderings to compose:

val byXOrdering = Ordering.by{ foo: Foo => foo.x }
val byYOrdering = Ordering.by{ foo: Foo => foo.y }
val byZOrdering = Ordering.by{ foo: Foo => foo.z }

// Compose byXOrdering and byYOrdering:
val byXThenYOrdering = Ordering.by{ foo: Foo => (foo, foo) }(Ordering.Tuple2(byXOrdering, byYOrdering))

// Compose byXOrdering and byYOrdering and byZOrdering:
val byXThenYThenZOrdering = Ordering.by{ foo: Foo => (foo, foo, foo) }(Ordering.Tuple3(byXOrdering, byYOrdering, byZOrdering))

But it is relatively "noisy". I could not find anything better using only the standard library, and so I would actually advise to use our own helper:

final class CompositeOrdering[T]( val ord1: Ordering[T], val ord2: Ordering[T] ) extends Ordering[T] {
  def compare( x: T, y: T ) = {
    val comp = ord1.compare( x, y )
    if ( comp != 0 ) comp else ord2.compare( x, y )
  }
}
object CompositeOrdering {
  def apply[T]( orderings: Ordering[T] * ) = orderings reduceLeft (_ orElse _)
}
implicit class OrderingOps[T]( val ord: Ordering[T] ) extends AnyVal {
  def orElse( ord2: Ordering[T] ) = new CompositeOrdering[T]( ord, ord2 )
}

Which can be used like this:

val byXOrdering = Ordering.by{ foo: Foo => foo.x }
val byYOrdering = Ordering.by{ foo: Foo => foo.y }
val byZOrdering = Ordering.by{ foo: Foo => foo.z }

// Compose byXOrdering and byYOrdering:
val byXThenYOrdering = byXOrdering orElse byYOrdering

// Compose byXOrdering and byYOrdering and byZOrdering:
val byXThenYThenZOrdering = byXOrdering orElse byYOrdering orElse byZOrdering

Or even simpler, like this:

// Compose byXOrdering and byYOrdering:
val byXThenYOrdering = CompositeOrdering(byXOrdering, byYOrdering)

// Compose byXOrdering and byYOrdering and byZOrdering:
val byXThenYThenZOrdering = CompositeOrdering(byXOrdering, byYOrdering, byZOrdering)

CompositeOrdering.apply is basically what you called Ordering.multipleBy in your question.

回答2:

If you want maximal speed--not what you asked for, I know!--and still decent clarity, you can

def compare(that: Foo): Int = {
  this.length compareTo that.length match { case 0 =>; case c => return c }
  this.x      compareTo that.x      match { case 0 =>; case c => return c }
  this.y.size compareTo that.y.size match { case 0 =>; case c => return c }
  this.z.head compareTo that.z.head match { case 0 =>; case c => return c }
  0
}

There are various nice collection-based and other solutions also, which I will leave to others to explain. (Note all the boilerplate and observe that all you really need to know is _.length in each case...which motivates a compareBy, for example.)

回答3:

The best I can think of is this:

def compare(that: Foo) = multiCompare(
  this.length compareTo that.length      // primary comparison
  this.x      compareTo that.x,          // secondary comparison
  this.y.size compareTo that.y.size,     // tertiary comparison
  this.z.head compareTo that.z.head,     // final tie breaker
)

def multiCompare(c: ( => Int)*) = c find {_ != 0} getOrElse 0