Describe Core PEG and Full PEG using GADTs

PEG.scala

object PEG {
  sealed trait Category
  class Full extends Category
  final class Core extends Full

  sealed trait Expression[+A]
  case class Alpha(ch: Char) extends Expression[Core]
  case class Choice[+A <: Category](lhs: Expression[A], rhs: Expression[A]) extends Expression[A]
  case class Sequence[+A <: Category](lhs: Expression[A], rhs: Expression[A]) extends Expression[A]
  case class Repeat0[+A <: Category](body: Expression[A]) extends Expression[A]
  case class Not[+A <: Category](body: Expression[A]) extends Expression[A]
  case class Repeat1(body: Expression[Full]) extends Expression[Full]
  case class And(body: Expression[Full]) extends Expression[Full]

  def desugar(e: Expression[Full]): Expression[Core] = e match {
    case Alpha(ch) => Alpha(ch)
    case Choice(lhs, rhs) => Choice(desugar(lhs), desugar(rhs))
    case Sequence(lhs, rhs) => Sequence(desugar(lhs), desugar(rhs))
    case Repeat0(body) => Repeat0(desugar(body))
    case Not(body) => Not(desugar(body))
    case Repeat1(body) => Sequence(desugar(body), Repeat0(desugar(body)))
    case And(body) => Not(Not(desugar(body)))
  }

  def display(e: Expression[Core]): String = e match {
    case Alpha(ch) => s"'${ch}"
    case Choice(lhs, rhs) => s"(${display(lhs)}/${display(rhs)})"
    case Sequence(lhs, rhs) => s"(${display(lhs)} ${display(rhs)})"
    case Repeat0(body) => s"(${display(body)})*"
    case Not(body) => s"!(${display(body)})"
  }

  def main(args: Array[String]): Unit = {
    val e: Expression[Full] = Sequence(
      And(Choice(Alpha('a'), Alpha('b'))), Repeat1(Choice(Alpha('a'), Alpha('b')))
    )
    //(!(!(('a/'b))) (('a/'b) (('a/'b))*))
    println(display(desugar(e)))
  }
}: