Typeclass latices

Language Design
1

I have a recurrent problem when modelling typeclass hierarchies. So let’s start with a simple example:

trait Monoid[T] {
  def apply(lhs: T, rhs: T): T
}

trait Semigroup[T] extends Monoid[T] {
  def zero: T
}

Now, the underlying logic that we want to expose is that monoids can be extended to a semigroup. Or to put it another way, if you have a semigroup, you can derive a monoid. Now, in interesting cases, we end up with branching patterns of inheritance – a latice of typeclasses. And because Semigroup extends Monoid, you end up with multiple, clashing instances, and all the mess that this gives us.

trait Monoid[T] { ... }
trait Semigroup[T] given Monoid[T] { ... }

This encoding avoids the inheritance. It means we can only make a semigroup when there is a corresponding monoid. But now when we use it, we need:

def someFunc[T] given (M: Monoid[T], S: Semigroup[T]) = ???

The list of implied instances rapidly explodes. However, given that we have a semigroup, we know there must be a monoid, because semigroup is defined as requiring a monoid. So we can recover this knowledge:

trait Monoid[T] { ... }
trait Semigroup[T] given (val monoid: Monoid[T]) { ... }
implied SemigroupsRequireMonoids [T] 
  given Semigroup[T] for Monoid[T] = the[Semigroup[T]].monoid

We can now write:

def foo[T] given Semigroup[T] = {
  the[Semigroup[T]] // from the given argument
  the[Monoid[T]]       // via SemigroupsRequireMonoids
}

Now, I freely admit that this is not beautiful. The typeclass lattice is being encoded here by a given val on the trait and is being unpacked by an implied instance that extracts it. However, it does avoid the multiple instances problem and the needing to pass everything in explicitly problem.

So I guess my question is if we can make language improvements for scala 3 that get rid of some of this pain. For example, a way of marking a given on a trait as “exporting” that implied value back out again. For example:

trait Semigroup[T] given (implied monoid: Monoid[T]) { ... }

so here, by marking the given monoid as implied, that makes it available again but without needing to expose a val or write the implicit extractor.

2

I proposed to resolve this when trait parameters were discussed:

3

I believe it’s a dead end to try to model typeclass hierarchies without inheritance.

On the other hand, the new implicit resolution rules enable a solution to the “branching patterns
of inheritance” problem. Notably, the fact that now nesting is taken into account:

trait Functor[F[_]] {
  def (x: F[A]) map [A, B] (f: A => B): F[B]
}
trait Applicative[F[_]] extends Functor[F] { ... }
trait Monad[F[_]] extends Functor[F] { ... }

def f1[F[_] : Applicative : Monad, T](x: F[T], g: T => T) = {
  x.map(g) // error: ambiguous
}

def f2[F[_] : Applicative : Monad, T](x: F[T], g: T => T) = {
  implied for Functor[F] = the[Monad[F]]
  x.map(g) // works!
}

So my take on branching patterns of inheritance is:

  • It’s best to avoid them. A hairy extension hierarchy is problematic no matter whether it’s about “OO” classes or “FP” typeclasses.
  • Where you do get branching inheritance, there’s a simple local fix to avoid ambiguities.
4

I believe it’s a dead end to try to model typeclass hierarchies without inheritance.

OK. I’d be interested to know why you think this. I’ve been playing with encoding core category theory using the non-inheritance scheme I outlined above, and so far it has worked out fine. But perhaps I’ve not done anything complicated enough yet. I have Category, Monoidal, Cartesian, Cocartesian, and then some DSLish categories for things like numbers. So far no inheritance, and not hit a problem. Just the boilerplate I outlined above.

5

OK. I’d be interested to know why you think this.

I don’t doubt that it’s possible. But it’s just that using nested implicit arguments instead of extends is more fragile and more expensive in terms of source-level boilerplate code needed, generated code, and execution time. A Monad is a Functor, so this is one of the places where using extends is the most obvious form to use.