GADT Type as Shapeless Coproduct -- how to build an Interpreter with an arbitrary number of Algebras

Question

Let say I have two GADT types.

  abstract class Numbers[A]()
  case class IntType() extends Numbers[Int]

  abstract class Letters[A]()
  case class EnglishType() extends Letters[String]

And I have an Interpreter for each of the GADT types which will print out a description for each of the GADT subtypes.

  trait Interpreter[ALG[_],A] {
    def description(a: ALG[A]) : String
  }

  case class NumbersInterpreter[A]() extends Interpreter[Numbers,A] {
    override def description(a: Numbers[A]): String =
      a match {
        case i: IntType => "Int"
      }
  }

  case class LettersInterpreter[A]() extends Interpreter[Letters,A] {
    override def description(a: Letters[A]): String =
      a match {
        case e: EnglishType => "English"
      }
  }

I'm looking to combine the two GADTs into a single GADT called All

  type All[A] = Numbers[A] :+: Letters[A] :+: CNil

I can create a new interpreter by hard-coding all the GADT values.

  case class DualInterpreter[A](
    numbersInterpreter: NumbersInterpreter[A],
    lettersInterpreter: LettersInterpreter[A]) extends Interpreter[All,A] {
    override def description(a: All[A]): String =
      a match {
        case Inl(num) => numbersInterpreter.description(num)
        case Inr(Inl(let)) => lettersInterpreter.description(let)
        case _ => sys.error("Unreachable Code")
      }
  }

However, I would like to add a bunch of GADT algebras and interpreters and arbitrarily combine them into a single algebra so I'm looking for a more generic approach to replace the DualInterpreter above. I can see the type signature is something along the lines of

  case class ArbitraryInterpreter[ALG[_]<:Coproduct,A](???) extends Interpreter[ALG,A] {
    override def description(a: ALG[A]): String = ???
  }

The main thing I would like to abstract away is the pattern matching inside of the description method because it could get pretty ugly with the number of available algebras. It would be have an interpreter where the constructor arguments are the interpreters and the pattern matching delegates to the appropriate interpreter based on the type ALG passed into the description method.

Mateusz Kubuszok Mateusz Kubuszok · Accepted Answer · 2020-03-06T09:54:12

You mean something like this?

// using kind projector
def merge[L[_], R[_] <: Coproduct, A](
  li: Interpreter[L, A],
  ri: Interpreter[R, A]
): Interpreter[Lambda[A => L[A] :+: R[A]] , A] =
  new Interpreter[Lambda[A => L[A] :+: R[A]] , A] {
    override def description(lr: L[A] :+: R[A]): String =
      lr match {
        case Inl(l) => li.description(l)
        case Inr(r) => ri.description(r)
      }
  }

perhaps with

implicit class InterpreterOps[L[_], A](val l: Interpreter[L, A]) extends AnyVal {

  def ++ [R[_] <: Coproduct](r: Interpreter[R, A]): Interpreter[Lambda[A => L[A] :+: R[A]] , A] = merge(l, r)
}

used as


type CNilF[A] = CNil // trick to make things consistent on kind-level
case class CNilInterpreter[A]() extends Interpreter[CNilF, A] {
  override def description(a: CNilF[A]): String = ???
}

def allInterpreter[A]: Interpreter[All, A] =
  // :+: is right associative, but normal methods are left associative,
  // so we have to use parens
  NumbersInterpreter[A]() ++ (LettersInterpreter[A]() ++ CNilInterpreter[A]())

GADT Type as Shapeless Coproduct -- how to build an Interpreter with an arbitrary number of Algebras

1 Answers