recursionschemescategorically.worksheet.sc

sealed trait Expr

case class Const(d: Double) extends Expr

case class Var(a: String) extends Expr

case class Times(l: Expr, r: Expr) extends Expr

case class Plus(l: Expr, r: Expr) extends Expr


val expr: Expr =
  Plus(Times(Var("x"), Var("x")),
    Plus(Times(Const(3.0), Var("x")),
      Const(4.0)))

def eval(expr: Expr): Double = {
  expr match {
    case Const(d) => d
    case Var(a) => a match {
      case "x" => 5
      case _ => throw new Exception("not supported")
    }
    case Plus(l, r) => eval(l) + eval(r)
    case Times(l, r) => eval(l) * eval(r)
  }
}

eval(expr)

def pretty(expr: Expr): String = {
  expr match {
    case Const(d) => s"$d"
    case Var(s) => s
    case Plus(l, r) => pretty(l) + " + " + pretty(r)
    case Times(l, r) => pretty(l) + " * " + pretty(r)
  }
}

pretty(expr)


sealed trait ExprF[R]

case class ConstF[R](d: Double) extends ExprF[R]

case class VarF[R](a: String) extends ExprF[R]

case class TimesF[R](l: R, r: R) extends ExprF[R]

case class PlusF[R](l: R, r: R) extends ExprF[R]

def evalF(expr: ExprF[Double]): Double = {
  expr match {
    case ConstF(d) => d
    case VarF(a) => a match {
      case "x" => 5
      case _ => throw new Exception("not supported")
    }
    case PlusF(l, r) => l + r
    case TimesF(l, r) => l * r
  }
}


def prettyF(expr: ExprF[String]): String = {
  expr match {
    case ConstF(d) => s"$d"
    case VarF(s) => s
    case PlusF(l, r) => l + " + " + r
    case TimesF(l, r) => l + " * " + r
  }
}

import cats._
import cats.implicits._

implicit val functor: Functor[ExprF] = new Functor[ExprF] {
  override def map[A, B](fa: ExprF[A])(f: A => B) = {
    fa match {
      case ConstF(d) => ConstF(d)
      case VarF(a) => VarF(a)
      case PlusF(l, r) => PlusF(f(l), f(r))
      case TimesF(l, r) => TimesF(f(l), f(r))
    }
  }
}

val plusF: ExprF[Double] = PlusF(1.2, 0.4)

evalF(plusF).toString

prettyF(plusF.map(_.toString))

def evalFtuple(expr: ExprF[(String, Double)]): (String, Double) = expr match {
  case ConstF(x) => ("Done", x)
  case VarF("x") => ("Done", 5)
  case VarF(_) => ("Done", 0)
  case TimesF((s, l), (_, r)) => (s, l * r)
  case PlusF((s, l), (_, r)) => (s, l + r)
}

def mkDone(x: Double): (String, Double) = ("Done", x)

evalFtuple(plusF.map(mkDone))

mkDone(evalF(plusF))

type Algebra[F[_], A] = F[A] => A

def evalFalg: Algebra[ExprF, Double] = {
  case ConstF(d) => d
  case VarF(a) => a match {
    case "x" => 5
    case _ => throw new Exception("not supported")
  }
  case PlusF(l, r) => l + r
  case TimesF(l, r) => l * r
}

def prettyFalg: Algebra[ExprF, String] = {
  case ConstF(d) => s"$d"
  case VarF(s) => s
  case PlusF(l, r) => l + " + " + r
  case TimesF(l, r) => l + " * " + r
}

def evalFtupleAlg: Algebra[ExprF, (String, Double)] = {
  case ConstF(x) => ("Done", x)
  case VarF("x") => ("Done", 5)
  case VarF(_) => ("Done", 0)
  case TimesF((s, l), (_, r)) => (s, l * r)
  case PlusF((s, l), (_, r)) => (s, l + r)
}

def j: Algebra[ExprF, Expr] = {
  case ConstF(d) => Const(d)
  case VarF(a) => Var(a)
  case PlusF(l, r) => Plus(l, r)
  case TimesF(l, r) => Times(l, r)
}

case class Fix[F[_]](unfix: F[Fix[F]])

object Fix {
  def in[F[_]](ff: F[Fix[F]]): Fix[F] = new Fix[F](ff)

  def out[F[_]]: Fix[F] => F[Fix[F]] = f => f.unfix
}

type Ex = Fix[ExprF]


def v(s: String): Ex = Fix(VarF(s))
def num(d: Double): Ex = Fix(ConstF(d))

def mul(l: Ex, r: Ex): Ex = Fix(TimesF(l, r))
def add(l: Ex, r: Ex): Ex = Fix(PlusF(l, r))

val ex1 = add(num(3.0), num(4.0))

val ex2 = add(mul(v("x"), v("x")), add(mul(num(3),v("x")), num(4)))

def cata[F[_]: Functor, A](alg: Algebra[F, A]): Fix[F] => A = {
  fix => Fix.out[F].andThen(_.map(cata(alg))).andThen(alg)(fix)
}

def mkExpr: Fix[ExprF] => Expr = cata(j)

mkExpr(ex1)

cata(prettyFalg).apply(ex2)
cata(evalFalg).apply(ex2)
cata(evalFtupleAlg).apply(ex2)