# 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.

- Rank N Types
- FunctionK
- GADT
- Phantom Types
- Dependent Types
- "First Class" Types
- Type Classes
- Generic Type Class Derivation

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.