Skip to content

Instantly share code, notes, and snippets.

@trane
Last active August 29, 2015 14:27
Show Gist options
  • Save trane/fa9a43e6e6774e9010a2 to your computer and use it in GitHub Desktop.
Save trane/fa9a43e6e6774e9010a2 to your computer and use it in GitHub Desktop.
playing with Coyoneda+Free Monad for algebraic Rings.. and funsies
import algebra._, std.int._
import cats._, free._, Free._
trait Expr[A]
case class Const[A](term: A) extends Expr[A]
case class Add[A](e1: Expr[A], e2: Expr[A])(implicit val r: Ring[A]) extends Expr[A]
case class Sub[A](e1: Expr[A], e2: Expr[A])(implicit val r: Ring[A]) extends Expr[A]
case class Mul[A](e1: Expr[A], e2: Expr[A])(implicit val r: Ring[A]) extends Expr[A]
type Exp[A] = FreeC[Expr, A]
def add[A : Ring](e1: Expr[A], e2: Expr[A]): Exp[A] =
liftFC(Add(e1, e2))
def sub[A : Ring](e1: Expr[A], e2: Expr[A]): Exp[A] =
liftFC(Sub(e1, e2))
def mul[A : Ring](e1: Expr[A], e2: Expr[A]): Exp[A] =
liftFC(Mul(e1, e2))
def const[A](a: A): Exp[A] =
liftFC(Const(a))
implicit def int2App(i: Int) =
Const(i)
def program: Exp[Int] =
for {
x <- add(1, 2)
y <- mul(2, x)
z <- sub(1, y)
} yield z
implicit val transform = new (Expr ~> Id) {
def apply[A](expr: Expr[A]): Id[A] = expr match {
case Const(a) => a
case a @ Add(e1: Expr[A], e2: Expr[A]) => a.r.plus(apply(e1), apply(e2))
case s @ Sub(e1: Expr[A], e2: Expr[A]) => s.r.minus(apply(e1), apply(e2))
case m @ Mul(e1: Expr[A], e2: Expr[A]) => m.r.times(apply(e1), apply(e2))
}
}
def compile[A](program: Exp[A])(implicit natx: Expr ~> Id): A =
runFC(program)(natx)
compile(program)
@davidhoyt
Copy link

See my fork for a working implementation (https://gist.github.com/davidhoyt/efdb7712c99e062ce6ce).

@trane
Copy link
Author

trane commented Aug 17, 2015

Thanks @davidhoyt 👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment