Last active
April 12, 2020 17:35
-
-
Save oli-kitty/4e7d094eab28f57b8312c9d12f7403de to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment