Defer could use some additional instances

[morgen-peschke]

Defer is really handy when writing typeclass instances for generic recursive ADTs, and unfortunately it's currently missing most of the instances that tend to be useful for this shape of data type.

I'd like to add Defer instances for the following typeclasses:

• Eq
• Order
• Hash
• Show

I'd also like to add Defer instances for these related typeclasses, mostly for completeness:

• Equiv
• Ordering
• PartialOrder
• PartialOrdering

As an example of how fiddly this can be, a simplified Test[A] has this shape:

sealed trait Test[A]
object Test {
  case class LessThan[A](a: A) extends Test[A]
  case class EqualTo[A](a: A) extends Test[A]
  case class GreaterThan[A](a: A) extends Test[A]
  case class Not[A](test: Test[A]) extends Test[A]
  case class Forall[A](tests: List[Test[A]]) extends Test[A]
  case class Exists[A](tests: List[Test[A]]) extends Test[A]

  implicit def show[A: Show]: Show[Test[A]] = ???
}

The sort of instance which would work for this if Test weren't generic looks like this:

 implicit def show[A: Show]: Show[Test[A]] = {
   Show.show {
     case LessThan(a)    => s"_ < ${a.show}"
     case EqualTo(a)     => s"_ = ${a.show}"
     case GreaterThan(a) => s"_ > ${a.show}"
     case Not(test)      => s"!(${test.show})"
     case Forall(tests)  => tests.mkString_("forall(", " && ", ")")
     case Exists(tests)  => tests.mkString_("exists(", " || ", ")")
   }
 }

scastie

Unfortunately, because it doesn't provide a stable implicit, it generates a new instance every time it recurses.

Implementing an anonymous subclass can avoid this, but only if an implicit self-reference is added:

  implicit def show[A: Show]: Show[Test[A]] =
    new Show[Test[A]] {
      implicit private val self: Show[Test[A]] = this

      def show(a: Test[A]): String = a match {
        case LessThan(a)    => s"_ < ${a.show}"
        case EqualTo(a)     => s"_ = ${a.show}"
        case GreaterThan(a) => s"_ > ${a.show}"
        case Not(test)      => s"!(${test.show})"
        case Forall(tests)  => tests.mkString_("forall(", " && ", ")")
        case Exists(tests)  => tests.mkString_("exists(", " || ", ")")
      }
    }

scastie

In comparison, Defer results in an idiomatic implementation that neatly avoids the easy errors of the other versions:

  implicit def show[A: Show]: Show[Test[A]] =
    Defer[Show].fix { implicit s =>
      Show.show {
        case LessThan(a)    => s"_ < ${a.show}"
        case EqualTo(a)     => s"_ = ${a.show}"
        case GreaterThan(a) => s"_ > ${a.show}"
        case Not(test)      => s"!(${test.show})"
        case Forall(tests)  => tests.mkString_("forall(", " && ", ")")
        case Exists(tests)  => tests.mkString_("exists(", " || ", ")")
      }
    }

scastie

[johnynek]

This is a really nice observation!

[rossabaker]

catsContravariantMonoidalForEq came up at work recently, and I was struggling to think of other times we provide instances for some other type class. It got me wondering whether there's some ancient taboo on this approach.

If nobody can remember why not, I think this is a splendid idea.

[johnynek]

@rossabaker I think we have actually just not implemented all the type-classes on type-classes that we have. We should add them. Especially the first order type classes F[_] like Eq, Hash, Order, Monoid, ... those have a lot of typeclasses. The second order type-classes F[_[_]] have some as well, but they are more abstract and we probably haven't noticed all of them yet.