Generic Type Class Derivation in Scala 3

I'm recently migrating some libs and projects to Scala 3, I guess it would be very helpful to me or anyone interested to learn some new functional programming features that Scala 3 is bringing to us.

Source code 👉 https://github.com/jcouyang/meow

From the previous article Type Classes, we know that it should be very straightforward to implement a Functor instance, e.g. for Option.

given Functor[Option] with
  def fmap[A, B](f: A => B): Option[A] => Option[B] = (oa: Option[A]) => oa match
    case Some(a) => Some(f(a))
    case None => None

However, there are so many data types to implement, and there is too much boilerplate for each new data type, although it is easy to do so.

Let's say we have a new ADT Tree:

enum Tree[T] {
  case Branch(left: Tree[T], right: Tree[T])
  case Leaf(elem: T)
}

If we want this Tree to be map-able, show-able, we need to implement Functor and Show instance for Tree.

Since Tree is an ADT, which means it can be represented as a generic type Product or Coproduct, this is where shapeless come in handy in Scala 2, and with some shapeless-based libs like Kittens, we can just simply derive these type class instances without actually implementing them.

Example in Kittens https://github.com/typelevel/kittens#derive-functor :

import cats.derived._
implicit val showTree: Show[Tree] = semiauto.show
implicit val functorTree: Functor[Tree] = semiauto.functor

In Scala 3, something like this is natively supported, it can be done without any lib.

Let's start with the simpler type class Show.

Kind 0 Type Class Derivation

Show is type class for A, since A is just a type, let us call A Kind 0 and A[_] Kind 1. To create a generic type class derivation natively in Scala 3, the steps are pretty similar to shapeless:

Find generic representation of type A, that is, break A into Product and Coproduct combinations
Implement instances for Product and Coproduct types.

For the impatient, the final result of generic Show derivation in Scala 3 will look like:

enum Tree[T] derives Show {
  case Branch(left: Tree[T], right: Tree[T])
  case Leaf(elem: T)
}

Yeah, it is that simple, just add derives Show to the data type.

Generic representation of `A`

Scala 3 is able to derive the generic representation of data types as Mirror[T] type https://dotty.epfl.ch/docs/reference/contextual/derivation.html#types-supporting-derives-clauses , in the same way shapeless' Generic[T] type did.

In our example, to derive the generic representation of Tree, we can simply define a derived function:

inline def derived[T](using m: Mirror.Of[T]): Show[T] =
  inline m match
    case s: Mirror.SumOf[T] => ???
    case p: Mirror.ProductOf[T] => ???

By using m: Mirror.Of[T], the compiler will automatically derive the Mirror.Of[T] type from T, which will look like:

new Mirror.Sum:
  type MirroredType = Tree
  type MirroredElemTypes[T] = (Branch[T], Leaf[T])
  type MirroredMonoType = Tree[_]
  type MirroredLabel = "Tree"
  type MirroredElemLabels = ("Branch", "Leaf")

  def ordinal(x: MirroredMonoType): Int = x match
    case _: Branch[_] => 0
    case _: Leaf[_] => 1

new Mirror.Product:
  type MirroredType = Branch
  type MirroredElemTypes[T] = (Tree[T], Tree[T])
  type MirroredMonoType = Branch[_]
  type MirroredLabel = "Branch"
  type MirroredElemLabels = ("left", "right")

  def fromProduct(p: Product): MirroredMonoType =
    new Branch(...)

new Mirror.Product:
  type MirroredType = Leaf
  type MirroredElemTypes[T] = Tuple1[T]
  type MirroredMonoType = Leaf[_]
  type MirroredLabel = "Leaf"
  type MirroredElemLabels = Tuple1["elem"]

  def fromProduct(p: Product): MirroredMonoType =
    new Leaf(...)

You don't have to memorize them all, we will get to each of these types shortly.

Since Tree is a Coproduct (Sum) type, we first need to figure out if it is a Branch or a Leaf to correctly represent the Tree data type.

Hence, the process to properly show Tree:

compiler derives Mirror.Of[Tree], the result is a Mirror.Sum
break into Mirror.Sum, if type is Mirror.ProductOf[Branch], recursively show its left and right
if type is Mirror.ProductOf[Leaf], recursively show its elem

Let's start with the simplest type, if our data type is a Leaf, how do we show it?

Generic instance of `Show[Product]` type

There is a singleton type MirroredLabel = "Leaf" we can use to show, and for whose elem, we can recursively derive Show instances for MirroredElemTypes

inline def summonAsList[T <: Tuple, F[_]]: List[F[Any]] =
  inline erasedValue[T] match
    case _: EmptyTuple => Nil
    case _: (t *: ts) => summonInline[F[t]].asInstanceOf[F[Any]] :: summonAsList[ts, F]

inline def derived[T](using m: Mirror.Of[T]): Show[T] =
  lazy val name = constValue[m.MirroredLabel]
  lazy val elemsShowInstances = summonAsList[m.MirroredElemTypes, Show]
  inline m match
    case s: Mirror.SumOf[T] => ???
    case p: Mirror.ProductOf[T] => ???

constValue[m.MirroredLabel] will get the singleton type's value, which is Leaf
summonAsList recursively find Show instance for each of Leaf's elements

Now we know the name of current type Leaf, and elemsShowInstances of Leaf's elements, let's try to fill the ??? with the actual implementation of Show[Product]

inline def derived[T](using m: Mirror.Of[T]): Show[T] =
  lazy val name = constValue[m.MirroredLabel]
  lazy val elemsShowInstances = summonAsList[m.MirroredElemTypes, Show]
  inline m match
    case s: Mirror.SumOf[T] => ???
    case p: Mirror.ProductOf[T] => new Show[T]:          // <- (ProductOf)
      def show(a: T): String =
        val elems = elemsShowInstances.iterator
          .zip(a.asInstanceOf[Product].prodIterator)     // <- (asInstanceOf)
          .map { _.show(_) }
        s"${name}(${elems.mkString(", ")})"

a.asInstanceOf[Product] looks really dangerous, but it's actually safe here, because we know that T is definitely a Product, so p must be a Mirror.ProductOf[T].

The implementation should be capable to derive Show for any type that has a Mirror.Product instance. Let's give it a try:

assertEquals(show(Leaf("leaf")), """Leaf("leaf")""")

But that doesn't work yet, because even we know how to show Product but, Leaf is one of the Tree Coproduct type.

Coproduct type has one more concept ordinal, if you have pay attention in the Mirror.Sum instance of Tree:

new Mirror.Sum:
  type MirroredType = Tree
  type MirroredElemTypes[T] = (Branch[T], Leaf[T])
  type MirroredMonoType = Tree[_]
  type MirroredLabel = "Tree"
  type MirroredElemLabels = ("Branch", "Leaf")

  def ordinal(x: MirroredMonoType): Int = x match
    case _: Branch[_] => 0
    case _: Leaf[_] => 1

That is, when Tree is constructed from Branch, the ordinal is 0, and the ordinal of Leaf's is 1.

By simply checking the ordinal of T, we can show T properly:

inline def derived[T](using m: Mirror.Of[T]): Show[T] =
  lazy val name = constValue[m.MirroredLabel]
  lazy val elemsShowInstances = summonAsList[m.MirroredElemTypes, Show]
  inline m match
    case s: Mirror.SumOf[T] => new Show[T]:
      def show(a: T): String =
        val ord = s.ordinal(a)   // <- (Ordinal)
        s"${insts(ord).asInstanceOf[Show[T]].show(a)}: ${name}"
    case p: Mirror.ProductOf[T] => new Show[T]:          
      def show(a: T): String =
        val elems = elemsShowInstances.iterator
          .zip(a.asInstanceOf[Product].prodIterator)
          .map { _.show(_) }
        s"${name}(${elems.mkString(", ")})"

Finally, let's verify that works as expected:

val aTree: Tree[String] = Branch(Leaf("l0"), Branch(Leaf("l1"), Leaf("r1")))
assertEquals(show(aTree), """Branch(Leaf("l0"): Tree, Branch(Leaf("l1"): Tree, Leaf("r1"): Tree): Tree): Tree""")

Kind 1 Type Class Derivation

If we try to do the same thing to create a generic Functor instance, it won't just work.

Because if we take a look closer look at the type class Show[A] and Functor[F[_]], you will notice that A in Show[A] is a simple type, or we can call it Kind 0 Type. But F in is higher kind, and we can call it Kind 1 Type here, because it must pass in a type to return a type. For example if F is List, you will need to pass a A to List to get a type List[A]. In other words, F is just a shortcut for [X] =>> F[X]. Type lambda: https://dotty.epfl.ch/docs/reference/new-types/type-lambdas.html

But, the structure of creating a generic Functor instance is pretty much the same as Show, except we need a special trick of Mirror for Kind 1 type.

inline given genFunctor[F[_]](using m: K1[F]): Functor[F] =
  lazy val functors = summonKindAsList[LiftP[Functor, m.MirroredElemTypes], Functor]
  inline m match
    case s: K1Sum[F] => ???
    case p: K1Product[F] => ???

Where K1 is simply a alias of Mirror

type K1[F[_]] = Mirror { type MirroredType[X] = F[X] ; type MirroredElemTypes[_] <: Tuple }
type K1Sum[F[_]] = Mirror.Sum { type MirroredType[X] = F[X] ; type MirroredElemTypes[_] <: Tuple }
type K1Product[F[_]] = Mirror.Product { type MirroredType[X] = F[X] ; type MirroredElemTypes[_] <: Tuple }

Which is just a little trick(I borrowed from shapeless source code) to basically add [_] to original K0 Mirror.

Mirror { type MirroredType = T; type MirroredElemTypes <: Tuple }

That's about it, and the rest of the implementation is pretty much the same as Show.

I will just leave the implementation of these ??? as an exercise, feel free to look up the answer in source code of meow, send me a PR if you find a better implantation.