6

Generic Type Class Derivation in Scala 3

 2 years ago
source link: https://blog.oyanglul.us/scala/dotty/en/generic-type-class-derivation
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Generic Type Class Derivation in Scala 3

Generic Type Class Derivation in Scala 3

Table of Contents

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

In the previous article Type Classes, we know it should be very straightforward to implement a Functor instance, i.e. 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 s many data types to implement, and there are too many boilerplate for each of new data type, even though it is simple to do so.

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 generic represented as Product or Coproduct, in Scala 2 that is where shapeless come in handy, and with some shapeless-based lib like Kittens, we can just directly derive these type class instances without actually implement them.

Example with Kittens: 

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

In Scala 3, such thing is natively support and 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 build a generic type class derivation natively in Scala 3, the steps are pretty similar to how shapeless:

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

For the impatient, the final result of generic Show derivation in Scala 3 will be 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 just 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], compiler will automatically derive the Mirror.Of[T] type from T, which will looks 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(...)

Don't need to memorize all of them for now, we will get to each of those types shortly.

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

Hence, the process to properly show Tree:

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

Let's start with the simplest type, when 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 its 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 in 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 actually it is safe here, because we know that T is definitely a Product so p is Mirror.ProductOf[T].

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

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

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 says if Tree is constructed from Branch, the ordinal is 0, and Leaf's ordinal 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(", ")})"

Let us verify if this will work 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 are trying to do the same thing to generate generic Functor instance, it won't just work.

Because if we look closer to 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 needs to pass in a type to return a type. For instance if F is List, you will need to pass a A to List to get a type List[A]. In another way, F is just short 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 small trick(I borrowed from shapeless source code) to basically add [_] to original K0 Mirror. 

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

That was pretty much it, and the rest of the implementation is pretty much the same as Show.

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK