Combinatorial explosion of implicit objects

Question

I have a case class, like this:

case class Container[T, M](value: T, modifier: M)

I want to make it possible to have an Ordering on Container for those T that have an Ordering too. I don't want to make T <: Ordered[T], because Container should be able to contain non-orderable values as well.

My first try was to implement Ordered, like this:

case class Container[T, M](value: T, modifier: M) extends Ordered[Container[T, M]] {
  override def compare(that: Container[T, M])(implicit ev: Ordering[T]): Int = ev.compare(value, that.value)
}

But that obviously doesn't work: because of the implicit parameter, compare no longer implements the trait.

So then I decided to try a type class approach:

class ContainerOrdering[T, M](implicit ev: Ordering[T]) extends Ordering[Container[T, M]] {
  override def compare(x: Container[T, M], y: Container[T, M]): Int = ev.compare(x.value, y.value)
}
implicit object ContainerOrderingInt extends ContainerOrdering[Int, Int]

This works (if I also import Ordering.Implicits._), but now I have a new problem: for every type M, I need a separate implicit object. Now there aren't too many types that I want to use in the M position (in fact, they all derive from a sealed trait that I define elsewhere), but still it means a combinatorial explosion of implicit objects that I need to define. I'm OK with having a separate implicit object for each T, but M really should be orthogonal to this.

There must be a better way to do this. Maybe I can leverage the fact that M extends a sealed trait. However, I haven't been able to do so. Any advice?

Conrad Conrad · Accepted Answer · 2015-07-27T11:57:52

Put the Ordering into a companion object!

object Container {
    implicit def ordering[T: Ordering, M] = new Ordering[Container[T, M]] {
        override def compare(x: Container[T, M], y: Container[T, M]): Int =
            implicitly[Ordering[T]].compare(x.value, y.value)
    }
}

Now you can use the ordering by using import Container._ where needed.

(PS: The real trick was of course to make the ordering implicit to free you from defining every single ordering for each possible type.)

Combinatorial explosion of implicit objects

1 Answers