Encoding type class hierarchies

Hello,

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.

11 Likes

This a bold and thought provoking proposal.

My initial worry would be that it would make working with Type Classes in Scala even more complicated than it is today. The implicit mechanism, which is used for derivations is already complex as it is and causes grief, especially to newcomers. Using it also for Type Class extending would aggravate this issue. Subclassing, traditionally used for extending, is much simpler. Even though Scala doesn’t have Type Classes/“traits” as an explicit feature, I feel that the Scala authors intended us to do them this way. That’s why the scheme outlined in Implicit scope and Cats is probably the best we can do, even though it has its issues (instances are in surprising places, non-deterministically chosen if a Type Class inherits from multiple other, …).

It’s also worth noting that, if I understand it correctly, other languages, like Rust or Haskell, do Type Class extensions in ways that are analogous to the traditional subclassing in Scala. I would also guess that they do it the Implicit scope and Cats way, no?

But I don’t want to discourage you, maybe you’re onto something! This idea definitely doesn’t deserve to fall of the table. I would be best, if other, more experienced Scala masters, who have been around longer than me, could chime in :pray: AFAIK this is not the first proposal for different encoding of Type Classes, there’s been scato and maybe others that haven’t even heard of. Only deeper experimentation and experience of Scala veterans could help us determine the pros/cons of this encoding.

1 Like

I’ve found a solution for problem 1: just use abstract classes. If we forgo inheritance, there is no reason to use traits anymore. So this works:

abstract class SubClass[X](using ev: => BaseClass[X])
  ...

I’m just quoting the official documentation for maximum effect:

It is a standard recommendation to prefer composition over inheritance. This is really an application of the principle of least power: Composition treats components as blackboxes whereas inheritance can affect the internal workings of components through overriding.

I have a partial solution for problem 2: export clauses. This works:

abstract class Semigroup[X]:
  def combine: (X, X) => X

abstract class Monoid[X](using ev: Semigroup[X]):
  export ev.combine
  def empty: X

def foldM[A](xs: List[A])(using M: Monoid[A]): A =
  xs.foldRight(M.empty)(M.combine)

However, there are four caveats:

  1. extension methods are not exported

Even though this compiles

abstract class Semigroup[X]:
  def combine: (X, X) => X
  extension (x: X) def <> (y: X): X = combine(x, y)

abstract class Monoid[X](using ev: Semigroup[X]) =
  export ev.{ combine, <> } // the extension method is exported
  def empty: X

This does not:

def foldM[A](xs: List[A])(using M: Monoid[A]): A =
  xs.foldRight(M.empty)(_ <> _)
[error] -- [E008] Not Found Error: /Users/regiskuckaertz/code/zio-prelude/core/shared/src/main/scala-dotty/zio/prelude/xp/Identity.scala:59:41 
[error] 59 |    xs.foldRight(M.empty)(_ <> _)
[error]    |                                       ^^^^
[error]    |value <> is not a member of A, but could be made available as an extension method.

This is a bummer, as one would have to duplicate the extension methods. Perhaps a bug?

  1. I had to pass the given by-value instead of by-name

Otherwise the compiler complains that ev is not stable:

[error] 21 |  export ev.*
[error]    |         ^^
[error]    |(Monoid.this.ev : => zio.prelude.xp.Semigroup[A]) is not a valid import prefix, since it is not an immutable path

This I feel is understandable knowing a little how by-name parameters are elaborated under the hood. If only Scala had first-class support for by-need parameters :thinking:

  1. I had to be explicit with what was exported

Otherwise a weird error came up:

[error] 22 |  export ev.*
[error]    |            ^
[error]    |            no eligible member * at Monoid.this.ev

Again, perhaps a bug?

  1. Dependencies are pushed at the instance definition site

So, to translate this:

Semigroup a => Semigroup (b -> a)
Monoid a => Monoid (b -> a)

you effectively need to do this:

Semigroup a => Semigroup (b -> a)
Semigroup a, Monoid a => Monoid (b -> a)

Despite all of this, I still feel like this is a much cleaner way of expressing the same intent and is also more powerful. For instance the definition of Semigroup a => Semigroup (b -> a) in the inheritance-based model would put both the library author and the library user in a sea of trouble.

oh, how did you come to that conclusion? I tried a very small subset of ZIO prelude, defining Associative and Identity for Chunk:

abstract class Associative[A]:
  def combine(l: => A, r: => A): A

object Associative:
  def make[A](combine0: (A, A) => A): Associative[A] = ...

  given [A] as Associative[Chunk[A]] =
    Associative.make(_ ++ _)

  given [A, B: Associative] as Associative[A => B] =
    Associative.make((f, g) => x => f(x) <> g(x))

abstract class Identity[A](using ev: Associative[A]):
  export ev.combine
  def identity: A

object Identity:
  def make[A: Associative](identity0: A): Identity[A] = ...
  
  given [A] as Identity[Chunk[A]] =
    Identity.make(Chunk.empty)

  given [A, B: Identity: Associative] as Identity[A => B] =
    Identity.make(_ => Identity[B].identity)

This is pretty close to how you would do it in Haskell (idk about Rust though).

5 Likes

Oh! Interesting. I was actually totally wrong on this. As you’re correctly pointing out, in Haskell (and Rust), the implementation for separate sub-classes/sub-traits is provided separately, not in one place as Scala/Implicit scope and Cats nudges us towards. (I would then guess that the final dictionaries with all the methods are created by the Haskell/Rust compiler, on the fly during compilation, from the dispersed implementations provided by the programmer.)

Your proposal is thus very very close to how Type classes are done in Haskell and Rust :+1:
It seems like I’ve been projecting my Scala-biased thinking onto those two languages :laughing:

1 Like

erf, caveat 3 is my mistake as I used the wrong wildcard character:

export ev._

works

1 Like

erf, I must have tested with an older release as caveat 1 does not hold anymore with M3. This is quite exciting! I took a small slice of Scalaz and rewrote it with this paradigm:

I really like how concise it is to define instances. As an author, I do not have the cognitive burden of doing SubClass ~> SuperClass translation in order to write/find them: that is completely gone. Nor do I need to put that burden on end users/future collaborators/students, etc.

Furthermore:

  • inheritance replaced with export directives makes intent declarative. Goodbye diamond hierarchies, now I can selectively export the implementations that I want. Case in point Monad:
abstract class Monad[F[_]](using ev1: Applicative[F], ev2: Bind[F]):
  export ev1._
  export ev2.{ bind, join }
end Monad

where both ev1 and ev2 export members of Apply, but they could well each have their own implementation that I’d have the luxury of choosing.

  • as alluded above, extension methods are also exported, that saves a lot of boilerplate:
abstract class Semigroup[A]:
  def append(x: => A, y: => A): A
  extension (x: A) def <> (y: A): A = append(x, y)

abstract class Monoid[A](using S: Semigroup[A]):
  export S._
  def zero: A

given ListFoldable: Foldable[List] with
    def foldMap[A, B: Monoid](f: A => B): List[A] => B = 
      _.foldLeft(zero)((b, a) => b <> f(a))

This is looking really promising.

4 Likes

By the way, there are alternative takes on Type Classes in Haskell too, e.g.

Maybe they contain some ideas that could help us with improving type class encoding in Scala.