Encoding type class hierarchies


First off, what a beautiful achievement Scala 3 is. I think the huge amount of efforts you have been putting on this project (over the past, what, 8 years?!!) is just incredible and the result is a language that is much more elegant and easy to understand.

I wouldn’t write just to congratulate you though :sweat_smile: so I hope you will forgive me for expressing a gripe I have with one particular aspect. If you look up how to implement type classes in the Dotty documentation, there are a couple of examples where hierarchies are defined as such:

trait BaseClass[X]:

trait SubClass[X] extends BaseClass[X]:

It is implied above that type class hierarchies are the same as class hierarchies. This seemingly natural assumption leads, imho, to extremely ugly code and terrible practices downstream, and goes against the “intent over mechanism” mantra. This gets very clear when we look at the problem of writing type class instances:

  1. For any type X, a single instance must be defined for the most specific type class this type can be installed in. This is almost an invariant that is imposed by the mechanism. To take a trivial example from the Dotty website, one can define a Monoid[List] but is almost forbidden to write a Semigroup[List]. If they do, they will not only have to duplicate a lot of code, but it will fall on the user to make the right incantation of imports that pleases the compiler.

Continuing on the same example, it does not make the life of type class authors easier. Let’s look at cats (this is the same problem everywhere):

  1. You won’t find a Monoid[Int]. Nope, you will need to look for CommutativeGroup[Int]. For deep class hierarchies, that doesn’t scale well, as it forces the author to bundle all type class members into one single object. The mental burden that is implicit there goes against the usability given (no pun intended) by the syntactic devices you designed to make users’ life easier at the use site.
    And it gets ugly real quick, as it makes the code less modular, harder to scan and also much harder to find. People who might want to learn why [A] =>> Either[E, A] forms a Functor by studying the code are in no luck, they will first have to find out that it is above all a MonadError.

Speaking of finding, the next problem is to decide where to place your instances. The scenario where one defines their own data type is pretty much solved, if you can live with the above, but what about the rest?

  1. You have two choices which are again entirely mechanism-based. First, lexical scope, the current solution of choice in both cats and scalaz, where the onus is on the user to find the right combination of imports (granted, the dotty compiler provides really helpful messages here).
    Or, use implicit scope, conjure up a diagram in your head and move all your most-specific instances upstream, into the most-generic type class’s companion object. This is the approach adopted by zio-prelude. If you were to look for the Traversable[List], you’d be forgiven to think you would find it in the Traversable companion: no, it is in the companion of Invariant, the root of the hierarchy.

I am sure there are many other annoying consequences to this simple design decision; I think it is clear from the above that it forces developers to hack around semi-solutions to please the compiler in order to limit the burden on the end user.

To come back to the original “intent over mechanism” schtick, i’d like to suggest the following formulation is the only one that makes sense:

trait BaseClass[X]:

trait SubClass[X](using ev: => BaseClass[X]):

This to me communicates that a SubClass for X implies the existence of a BaseClass for X. And it seems to me that it solves all the problems I mentioned, just by reading the declaration.

  1. Now I can install short and easy to read instances for List as a Semigroup and also as a Monoid, though I can only do the latter because the former is there. Isn’t that the the whole point? Even better, I can provide a lower-priority instance of Functor[A] from Monad[A] if I want to, because the implicit proof is lazy:
object Monad:
  given functorFromMonad[F[_]](using Monad[F]) as Functor[F]:
    def map[A, B](f: A => B) =
      fa => fa.flatMap(a => summon[Monad[F]].pure(f(a)))
end Monad

2 and 3 are immediately solved too, as there is no incentive to place instances anywhere else than where they make sense: in the companion of the specific type class.

I have been playing with the encoding above, and it makes writing type class hierarchies much more elegant and idiomatic. The only downsides that I have found so far are:

trait Semigroup[A]:
  def combine: (A, A) => A
  extension [A](x: A) def <> (y: A): A = combine(x, y)
trait Monoid[A](using ev: => Semigroup[A]):
  def empty: A

then I could not do something like

trait Applicative[F[_]](using ev: Functor[F]):
  def pure[A]: A => F[A]
  def zip[A, B]: (F[A], F[B]): F[(A, B)]
object Applicative:
  given tupleApplicative[X: Monoid] as Applicative[[A] =>> (X, A)]:
    def pure[A] = (summon[Monoid[X]], _) // works
    def zip[A, B] = (x, y) => (x._1 <> y._1, (x._2, y._2)) // breaks, <> does not exist

I would have to add a Semigroup context bound too. Still, these seem like very small sacrifices compared to all of the above, and I’m not a compiler write but they sound like not insurmountable problems :thinking:

Right, apologies for this long tirade, I had to get it off my chest and submit it to you, in the hope that either I have failed to see something obvious or there is some real potential in the above.