A functional comparer

One of the aspects of Scala and Java that I've always felt could be improved is the mechanism for comparing things. The basic scheme, inherited from Java, is that two objects, x and y, can be compared and if the result is less than zero, then x is smaller than y, if it's greater than zero, then x is larger than y, otherwise they are equal. This is the kind of code which we need to write for some user-defined class:

case class Date(year: Int, month: Int, day: Int) extends Ordered[Date] {
  def compareTo(that: Date): Int = {
    val cfy = year.compareTo(that.year)
    if (cfy!=0) cfy
    else {
      val cfm = month.compareTo(that.month)
      if (cfm!=0) cfm
      else day.compareTo(that.day)
    }
  }
}

Part of the problem arises from the use of an Int (int in Java) that tries to represent three-valued logic with four billion different values. Java has no easy construct to switch according to ranges of values. Maybe in Java 12, the new switch statement will accommodate this requirement?

In Scala, at least, we could use pattern matching so that the code (above) to discriminate the results could be rewritten:

case class Date(year: Int, month: Int, day: Int) extends Ordered[Date] {
  def compare(that: Date): Int = year.compareTo(that.year) match {
    case 0 => month.compareTo(that.month) match {
      case 0 => day.compareTo(that.day)
      case x => x
    }
    case x => x
  }
}

But it's not really a lot better. Given that Scala is a functional language, I think we can improve things significantly. How about something like the following?

object Date {
  implicit val dateComparer: Comparer[Date] = {
    val cf = implicitly[Comparer[Int]]
    cf.snap(_.year) orElse cf.snap(_.month) orElse cf.snap(_.day)
  }
}

This time, we get an implicit Comparer[Int] (see below) and we compose the three necessary comparisons together.

Comparer[T] is a trait which defines an apply function of type T => T => Comparison. There are various methods for composing comparers, and there are methods which make it easy to compare things using the more usual tupled parameters (rather than the curried apply function). Comparison is a trait which can be evaluated as a Kleenean (three-valued logic type) and ultimately as an Option[Boolean].

We are able to perform the Date comparison (above) because the result of invoking each of the snap methods is one object: a Comparer[Date].  The orElse method composes comparers together such that, if there is a distinction yielded by the left-hand operand, then that is the result, otherwise we look to the right-hand operand, and so on.

We find an implicit value of a type class for the integer comparer, and we make this a variable called cf. The snap method takes a "lens" function as its parameter and transforms the Comparer[Int] into a Comparer[Date]

Actually, we can come up with something rather more elegant than this:

object Date {
  implicit val dateComparer: Comparer[Date] = Comparer.same[Date] :| (_.year) :| (_.month) :| (_.day)
}

The Comparer.same method simply provides a Comparer of the given type which always evaluates to Same. The :| method composes (using orElse) two Comparers where the one on the right is constructed from an implicitly discovered Comparer of the type yielded by the lens function and which is then snapped by the given lens. Here, the lens functions are defined as lambdas (function literals).

There's also a :|! method which works the same except that it invokes the orElseNot method which flips the sense of the Comparer formed from the lens function.

Actually, since in this case the lens functions are all of type Date=>Int and all of the same sense, we can do even better:

object Date {
  implicit val dateComparer: Comparer[Date] = Comparer(_.year, _.month, _.day)
}

Now, isn't that a lot more elegant? The apply method takes a variable list of lens functions but, in this form, they must all be of the same type.

Now, we've got the compiler doing some serious work for us. For each of the lens functions, the compiler will find an implicit Comparer and apply the lens function to it (via snap).

A typical usage of this in a specification might be:

val today = Date(2019, 6, 5)
val tomorrow = Date(2019, 6, 6)
Compare(today, today) shouldBe Same
Compare(today, tomorrow) shouldBe Less
Compare(tomorrow, today) shouldBe More

Well, of course, that's not quite it. We can do even better:

object MyComparers extends Comparers {
  val comparer: Comparer[Date] = comparer3(Date)
}
import MyComparers._
Compare(tomorrow, today) shouldBe More

This time, we didn't have to spell out how to compare the various elements of the Date case class. The compiler figured it out for us using the magic of type inference. Notice that we simply pass in the Date.apply method to the comparer3 method. But, inside comparer3, that method is never actually invoked. The work is all done by the compiler.

Now, we've really got the compiler doing some serious work for us!

As well as comparing case class instances made up of simple types such as String, Int, etc. we can also create case classes based on collections, wrappers, user-defined types, tuples, whatever. Just as long as there is an implicit Comparer[T] of the appropriate underlying type defined in scope.

So, for example, suppose that we have the following bizarre case class:

case class Bizarre(x1: Seq[Int], x2: (Double,Double), x3: Try[Boolean], x4: Option[Int], x5: Unit)
object MyComparers extends Comparers {
  implicit val comparer: Comparer[Bizarre] = comparer5(Bizarre)
}
import MyComparers._
val x1 = Bizarre(Seq(1, 2), (1.0, 0.0), Success(true), Some(4), ())
val x2 = Bizarre(Seq(1, 2), (1.0, 0.0), Success(true), Some(5), ())
Compare(x1,x2) shouldBe Less

We need do no more than declare the comparer implicitly.

Couldn't we have achieved all of this simply by comparing tuples using Ordering? To some extent, yes--if you just want to compare two tuples of the same arity and are happy with the -1, 0, +1 result. However, it's a little awkward and it doesn't happen implicitly for a case class. You must first invoke unapply in order to yield an Option[TupleN...]. And that will only work up to Tuple8. The comparers defined in the Compare package work with up to 11 parameters. And, even then, it would require a lot of code if the case class wasn't defined in decreasing order of significance.

The main purpose of the Comparer package is the elegance and the ease of composition of comparers and the provision of out-of-the-box comparisons for just about every situation. You can find this open-source package on github: https://github.com/rchillyard/Comparer.