Recursive DSLs

[julienrf]

Consider the following DSL:

import cats.free.Free
import cats.free.Free.liftF

sealed trait Expr[A]
case class Lit(value: Int) extends Expr[Int]
case class Add[A](lhs: Free[Expr, A], rhs: Free[Expr, A]) extends Expr[A]

object Expr {
  def lit(value: Int): Free[Expr, Int] = liftF(Lit(value))
  def add[A](lhs: Free[Expr, A], rhs: Free[Expr, A]): Free[Expr, A] = liftF(Add(lhs, rhs))
}

type Eval[A] = Int
object Eval extends (Expr ~> Eval) {
  def apply[A](expr: Expr[A]): Eval[A] =
    expr match {
      case Lit(value) => value
      case Add(lhs, rhs) => lhs.foldMap(Eval) + rhs.foldMap(Eval)
    }
}

Note that the Add constructor is recursive.

When using freek, however, we don’t fix the effective Free[Xxx, A] type into which case class constructors are lifted, so I don’t see how I can define my Add case class.

Any idea?