Encoding type class hierarchies

Language Design
21

I’ve been poking at Regis’s idea as well, and the only real pain-point I could find is that it’s really heavy on the imports at the call site. I think this is a philosophical design decision, as the fix is pretty straightforward: use a hybrid of both encodings by declaring the relationships within the companion objects:

abstract class Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}
object Functor {
  extension [F[_],A](fa: F[A]) def map[B](f: A => B)(using F: Functor[F]): F[B] = F.map(fa)(f)  
  given [F[_]](using a: Applicative[F]): Functor[F] = a.functor
  given [F[_]](using t: Traverse[F]): Functor[F] = t.functor
}

abstract class Applicative[F[_]](implicit val functor: Functor[F]) {
  def pure[A](a: A): F[A]
}
object Applicative {
  extension [A](a:A) def pure[F[_]](using A: Applicative[F]): F[A] = A.pure(a)
  given [F[_]](using m: Monad[F]): Applicative[F] = m.applicative
}

One of the things that I rather like about this approach is it almost completely removes the import tax at the call site, only leaving the extension methods to be explicitly imported.

Admittedly, it doesn’t directly solve the ambiguous givens problem with Monad and Traverse. On the bright side, because they no longer share a direct type relationship, the fix is much simpler:

def bar[F[_]](using m: Monad[F], t: Traverse[F]): F[Int] = {
  import t.given // as expected, m.given would work as well
  ???
}

Scastie playground with a minimal-ish working example

1 Like
22

Inheritance might still be useful even with this encoding, but as an alternative to using newtypes when picking a typeclass instance.

For example:

trait Monoid[A] extends Typeclass:
  def identity: A
  extension (left: A) def <>(right: A): A

trait Additive[A] extends Monoid[A]
trait Multiplicative[A] extends Monoid[A]

given Additive[Int] with
  def identity: Int = 0
  extension (left: Int) def <>(right: Int): Int = left + right

given Multiplicative[Int] with
    def identity: Int = 1
    extension (left: Int) def <>(right: Int): Int = left * right

def fold[A: Monoid](as: List[A]): A =
  as.foldLeft(Monoid[A].identity)(_ <> _)
  
fold(List(1, 2, 3)) // ambiguous: both Additive[Int] and Multiplicative[Int] match type Monoid[Int]

fold(List(1, 2, 3))(using Additive[Int]) // ok
fold(List(1, 2, 3))(using Multiplicative[Int]) // ok

if there is a single valid implementation (eg. for String) then we can just implement the base class as usual.

23

That would mostly work, the problem with fixing it like that, in my opinion, is that it’s not very extensible.

If you had a hypothetical library that provided Functor and Applicative and you wanted to add Monad, there would be no way to add the conversions to the base classes without modifying the library.

I think this was basically what they tried to do with the scato encoding (although that was slightly more complicated :smiley:).

24

While true, that would just take you back to having to do the imports manually, and if we can avoid that in most cases, it’s not terrible if it’s still something that has to be done in some corner cases.

Stated another way, given the choice between the two, I know which one I’d choose:

Vanilla Regis

def external[F[_]](given monad: Monad[F]): Functor[Foo] = {
  import monad.given
  summon[Functor[F]]
}
def internal[F[_]](given applicative: Applicative[F]): Functor[Foo] = {
  import applicative.given
  summon[Functor[F]]
}

Regis with best-effort linking

def external[F[_]](given monad: Monad[F]): Functor[Foo] = {
  import monad.given
  summon[Functor[F]]
}
def internal[F[_]](given applicative: Applicative[F]): Functor[Foo] = {
  summon[Functor[F]]
}