rchillyard / comparer

A functional (three-way) comparer for Scala

GitHub

Codacy Badge

Comparer CircleCI

A functional (three-way) comparer.

Introduction

Why do I say that this is a functional comparer? Because Comparers can be composed!

The old object-oriented way

Let's take a look at a typical date comparison using the built-in comparisons provided by Scala (and, ultimately, Java):

case class Date(year: Int, month: Int, day: Int) extends Ordered[Date] {
  def compare(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)
    }
  }
}

A typical usage of this in a specification might be:

val today = Date(2019, 6, 5)
val tomorrow = Date(2019, 6, 6)
today.compareTo(today) shouldBe 0
today.compareTo(tomorrow) shouldBe -1
tomorrow.compareTo(today) shouldBe 1

Yes, I know that we could also have used Ordering, which would have involved declaring an Ordering of Date in the companion object of Date.

It would look like this:

  object Date {
    trait OrderingDate extends Ordering[Date] {
      def compare(d1: Date, d2: Date): Int = {
        val cfy = d1.year.compareTo(d2.year)
        if (cfy != 0) cfy
        else {
          val cfm = d1.month.compareTo(d2.month)
          if (cfm != 0) cfm
          else d1.day.compareTo(d2.day)
        }
      }
    }
    implicit object OrderingDate extends OrderingDate
  }

And we wouldn't need the mixin of Ordered of Date in the case class any more.

A typical usage of this in a specification might be:

val today = Date(2019, 6, 5)
val tomorrow = Date(2019, 6, 6)
val ordering = implicitly[Ordering[DateJ]]
ordering.compare(today, today) shouldBe 0
ordering.compare(today, tomorrow) shouldBe -1
ordering.compare(tomorrow, today) shouldBe 1

This looks a little more like the functional version below. But the compare method itself is still very inelegant with all of those temporary variables.

Note that the 0, 1 and -1 values almost rise to the level of magic numbers. They have a significance that is far above their actual values. Indeed, if you performed the same comparison on an object with _String_s, the negative and positive values could be anything at all.

The new functional way

Now, let's look at the functional way of doing comparisons, using the Comparer library:

case class Date(year: Int, month: Int, day: Int)

Note that this (the case class) is just the same as the previous Date.

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

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 of Int into a Comparer of 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 Compare.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 lambda and which is then snapped by the given lens.

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 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, we never actually have to invoke that apply method. The work is all done by the compiler.

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

API

The chief methods of the API are as follows:

Comparer

Comparer extends the (curried) function T => T => Comparison. This makes sense since the T values being compared are not related and so don't naturally form part of a tuple. It also allows the use of a partially applied comparer. Note that, when curried parameters are used, we compare the outer (last) parameter with the inner, whereas when tupled parameters are used, it is conventional to compare the first parameter the second.

trait Comparer[T] extends (T => T => Comparison) {

  /**
    * Method to convert this Comparer[T] into an Ordering[T] which can then be used for more typical Java/Scala-style comparisons.
    *
    * @return a new Ordering[T].
    */
  def toOrdering: Ordering[T]

  /**
    * The following methods are defined both in tupled and curried signatures (only the tupled forms are shown here).
    * When you use these tupled forms, the compiler doesn't need an extra set of parentheses.
    */
  def >(tt: (T, T)): Boolean

  def <(tt: (T, T)): Boolean

  def ==(tt: (T, T)): Boolean

  def >=(tt: (T, T)): Boolean

  def <=(tt: (T, T)): Boolean

  def !=(tt: (T, T)): Boolean

  /**
    * Method to apply a lens function U=>T to this Comparer[T], resulting in a Comparer[U].
    * The U values that are the inputs to the resulting Comparer, are passed to the lens function to
    * yield a suitable pair of T values which can then be passed into this Comparer.
    *
    * I originally considered this the infamous "unMap" method which is part of an un-monad.
    * Observe that the lens function is U=>T instead of T=>U which would be the parameter of a monadic map method.
    * In case you're wondering, an un-monad is the wrappee as opposed to the wrapper (which would be a monad).
    * However, I think it makes slightly more sense to call this snap because it creates something (kind of like a picture)
    * by using a lens.
    *
    * @param lens a function which takes a U and returns a T.
    * @tparam U the underlying type of the returned Comparer.
    * @return a Comparer[U].
    */
  def snap[U](lens: U => T): Comparer[U]

  /**
    * A method to compose this Comparer with another Comparer of a different underlying type.
    *
    * @param uc a Comparer[U].
    * @tparam U the underlying type of uc.
    * @return a Comparer of tuples each comprising a T and a U.
    */
  def compose[U](uc: => Comparer[U]): Comparer[(T, U)]

  /**
    * Compose this Comparer with another Comparer of the same underlying type.
    *
    * There is also a similar method orElseNot which flips the sense of tc.
    *
    * @param tc the other Comparer (lazily evaluated).
    * @return the result of applying this Comparer unless it yields Same, in which case we invoke the other Comparer.
    */
  def orElse(tc: => Comparer[T]): Comparer[T]

  /**
    * A non-monadic transform method which transforms this Comparer into a different Comparer,
    * but of the same underlying type. NOTE: this was formerly called map.
    *
    * @param f the function which takes a Comparison and yields a different Comparison.
    * @return a new Comparer[T].
    */
  def transform(f: Comparison => Comparison): Comparer[T]

  /**
    * Method to invert the sense of a Comparer.
    *
    * @return a Compare[T] which, given the same tuple of Ts, yields the complementary Comparison to this Comparer.
    */
  def invert: Comparer[T]

  /**
    * Method to compose this Comparer[T] with a "lens" function that operates on a T.
    * See, for example, the definition of the Comparer in object Date (in CompareSpec).
    *
    * The resulting Comparer[T] is formed by using orElse to compose this Comparer[T] with a Comparer[T] that:
    * is formed by using the "lens" function lens to snap (the implicit) comparer (which is a Comparer[U]) into a Comparer[T].
    *
    * This method is used primarily when chaining together several Comparers, each of which is derived from the given function
    * by invoking snap on an implicitly-defined Comparer, with the a specified function.
    * The initial value is typically provided by the "same" method of Comparer's companion object.
    * 
    * There is a similar method :|! which invokes orElseNot instead of orElse.
    *
    * @param lens a function which takes a T (the underlying type of this and the result) and returns a U.
    * @tparam U the underlying type of the implicit comparer.
    * @return a Comparer[T] which is composed from this and the unmapped form of comparer.
    */
  def :|[U: Comparer](lens: T => U): Comparer[T]
}

object Comparer {

  /**
    * A method to construct a Comparer which always evaluates to Same.
    * This is used, for example, in the apply method following.
    *
    * @tparam T the underlying type of the Comparer.
    * @return a Comparer[T] which always evaluates to Same.
    */
  def same[T]: Comparer[T]

  /**
    * The following Comparers are defined for the common scalar types.
    */
  implicit val unitComparer: Comparer[Unit]
  implicit val byteComparer: Comparer[Byte]
  implicit val charComparer: Comparer[Char]
  implicit val shortComparer: Comparer[Short]
  implicit val intComparer: Comparer[Int]
  implicit val booleanComparer: Comparer[Boolean]
  implicit val stringComparer: Comparer[String]
  implicit val doubleComparer: Comparer[Double]
  implicit val floatComparer: Comparer[Float]
  implicit val longComparer: Comparer[Long]
  implicit val bigIntComparer: Comparer[BigInt]
  implicit val bigDecimalComparer: Comparer[BigDecimal]

  /**
    * The following Comparers are defined for the first four tuple types.
    * If you are looking for comparisons of more complex tuples, then use Ordering instead.
    * Alternatively, create a case class and then create a Comparer by extending Comparers and invoking comparerN where N is the number of fields.
    */
  implicit def tuple2[T1: Comparer, T2: Comparer]: Comparer[(T1,T2)]
  implicit def tuple3[T1: Comparer, T2: Comparer, T3: Comparer]: Comparer[(T1,T2,T3)]
  implicit def tuple4[T1: Comparer, T2: Comparer, T3: Comparer, T4: Comparer]: Comparer[(T1,T2,T3,T4)]
  implicit def tuple5[T1: Comparer, T2: Comparer, T3: Comparer, T4: Comparer, T5: Comparer]: Comparer[(T1,T2,T3,T4,T5)]
  implicit def tuple6[T1: Comparer, T2: Comparer, T3: Comparer, T4: Comparer, T5: Comparer, T6: Comparer]: Comparer[(T1, T2, T3, T4, T5, T6)]
  implicit def tuple7[T1: Comparer, T2: Comparer, T3: Comparer, T4: Comparer, T5: Comparer, T6: Comparer, T7: Comparer]: Comparer[(T1, T2, T3, T4, T5, T6, T7)]
  implicit def tuple8[T1: Comparer, T2: Comparer, T3: Comparer, T4: Comparer, T5: Comparer, T6: Comparer, T7: Comparer, T8: Comparer]: Comparer[(T1, T2, T3, T4, T5, T6, T7, T8)]  
  implicit def tuple9[T1: Comparer, T2: Comparer, T3: Comparer, T4: Comparer, T5: Comparer, T6: Comparer, T7: Comparer, T8: Comparer, T9: Comparer]: Comparer[(T1, T2, T3, T4, T5, T6, T7, T8, T9)]

  /**
    * Implicit converter from Ordering[T] to Comparer[T].
    *
    * @param to the Ordering[T] to be converted.
    * @tparam T the underlying type of to and the result.
    * @return a Comparer[T] which has the same intrinsic behavior as "to".
    */
  implicit def convert[T](to: Ordering[T]): Comparer[T]
  
object Compare {
  /**
    * Method to construct a Comparison from two objects of type T (tupled form).
    * The sense of the result of this comparison is the same as,
    * for example, Double.compare(t1, t2).
    *
    * @param t1 the first T.
    * @param t2 the second T.
    * @tparam T the type of both t1 and t2, such type providing implicit evidence of a Comparer[T].
    * @return a Comparison, resulting from applying the comparer to the tuple of t1 and t2.
    */
  def apply[T: Comparer](t1: T, t2: T): Comparison = Comparison(t2)(t1)
}

Comparison

From the application programmer's perspective, the following methods of Comparison are important:

sealed trait Comparison extends (() => Kleenean) {

  /**
    * Method to eagerly evaluate this Comparison.
    *
    * @return a Kleenean.
    */
  def apply(): Kleenean

  /**
    * Method to yield logical AND with short-circuit logic.
    *
    * @param c the other Comparison (lazily evaluated).
    * @return a Comparison according to Kleenean logic.
    */
  def &&(c: => Comparison): Comparison

  /**
    * Method to yield logical OR with short-circuit logic.
    *
    * @param c the other Comparison (lazily evaluated).
    * @return a Comparison according to Kleenean logic.
    */
  def ||(c: => Comparison): Comparison

  /**
    * Method to return the Java-style value of this Comparison.
    *
    * @return if Same then 0 else if Different(true) then -1 else 1
    */
  def toInt: Int

  /**
    * Method to compose this with another Comparison.
    * That is to say we yield either this or, in the case that this is Same, a default value of Comparison.
    *
    * @param c the other Comparison (lazily evaluated).
    * @return the composition of this and c.
    */
  def orElse(c: => Comparison): Comparison

  /**
    * Method to yield the complementary Comparison to this Comparison, that's to say the result is flipped (i.e. negated).
    *
    * @return Same if this Comparison is Same else the complementary (flipped) value of Different.
    */
  def flip: Comparison
}

/**
  * Case class which represents a Comparison which is different.
  *
  * @param less true or false. By conventions, we yield a true value when we compare a lesser object with a greater object.
  */
case class Different(less: Boolean) extends Comparison {
  // methods implemented as appropriate
}

/**
  * Case class which represents sameness (two objects compare as equal).
  */
case object Same extends Comparison {
  // methods implemented as appropriate
}

/**
  * Companion object for Comparison.
  */
object Comparison {
  /**
    * Different(false)
    */
  val More: Comparison
  /**
    * Different(true)
    */
  val Less: Comparison

  /**
    * Method to construct a Comparison from two objects of type T (curried form).
    * NOTE: the sense of the result will be similar to invoking, for example, Double.compare(t1, t2).
    * @param t2 the inner T.
    * @param t1 the outer T.
    * @param comparer an implicit Comparer[T].
    * @tparam T the type of both t1 and t2, which type must also provide implicit evidence of type Comparer[T].
    * @return a Comparison, resulting from applying the comparer to the tuple of t1 and t2.
    */
  def apply[T](t2: T)(t1: T)(implicit comparer: Comparer[T]): Comparison
}

Kleenean

The result of evaluating a Comparison is a Kleenean: a three-valued logic type. Kleenean evaluates to an Option of Boolean.

Comparers

This trait provides methods to create a Comparer for a case class (or other Product). It assumes that the parameters of the case class are in order of significance: most to least. All the programmer needs to do is to create an object which extends Comparers, and create a variable using the comparerN method with the appropriate value of N (according to the number of parameters).

case class Composite(i: Int, s: String)
object MyComparers extends Comparers {
  val compositeComparer: Comparer[Composite] = comparer2(Composite)
}

You may have to give the name of the apply function explicitly in some cases (for example, when there is a companion object).

There are additionally, implicit methods which will create a Comparer for a wrapper of a type. Currently defined are:

  • comparerIterable: Comparer[Iterable[T]]
  • comparerSeq: Comparer[Seq[T]]
  • comparerList: Comparer[List[T]]
  • comparerArray: Comparer[Array[T]]
  • comparerOpt: Comparer[Option[T]]
  • comparerTry: Comparer[Try[T]]
  • comparerEither: Comparer[Either[,T]]_

So, if your case class happens to include an iterable (sequence or list), array, optional, try or "either" types, you can still use one of the comparerN methods and the types will be handled. You don't have to do anything in your code (other than importing the implicits) to get the benefit of this feature. The comparerN methods are implemented up through N = 11.

What if the case class you want to compare doesn't have its fields in descending order of significance? For example, you might be using a Date class where the fields are laid out: day, month, year. There is a set of function manipulation methods in generic.Functional. For instance, for the situation mentioned, you can simply write something like the following:

    case class DateJ(day: Int, month: Int, year: Int)
    object MyComparers extends Comparers {
      import Functional._
      val comparer: Comparer[DateJ] = comparer3(invert3(DateJ))
    }

If you have a more complex situation, such as only needing to invert the first two parameters, please see ComparersSpec.

Colophon

This project has 100% coverage so it makes sense to resolve any doubtful points about usage by consulting the specifications (i.e. unit tests).

Versioning

Version 1.0.1 introduces the notion of curried parameters for the internal workings and for some of the application-oriented methods. This is a more functional approach and gives us the invaluable option of easily creating partially applied functions.

Version 1.0.2 introduces a Comparers trait which allows a programmer easily to get a comparer for a case class, assuming that the fields are in order from most to least significant.

Version 1.0.3 adds compareIterable, compareList, compareArray, compareTry, compareEither and compare7 thru compare10. Also Comparer of Boolean.

Version 1.0.4 adds Functional module and provides support for Scala 2.13

Version 1.0.5 introduced the Kleenean trait and has Comparison return it with apply(). Otherwise, no logic changes.

Version 1.0.6 merged 1.0.5 with master branch.

Version 1.0.7 improved usability slightly by moving compare method of Comparison into apply method of (new) Compare object.

Version 1.0.8 improved support for comparing tuples.