Going bananas with recursion schemes for expression evaluation

“Going bananas with
recursion schemes for
fixed point data types”

Elegance of Functional Programming

Can we actually
can Build some
Stuff?

Recursive Structures are common

●
○
■
■
○
■
■

●
○
■
■
○
■
■
●
○
○
○

●
○
■
■
○
■
■
●
○
○
○
●

Expressions!
Square
Sum
Square
10
Multiply
10 10

data Exp = IntVal Int |
DecVal Double |
Sum Exp Exp |
Multiply Exp Exp |
Divide Exp Exp |
Square Exp
sealed trait Exp
final case class IntValue(v: Int) extends Exp
final case class DecValue(v: Double) extends Exp
final case class Sum(exp1: Exp, exp2: Exp) extends Exp
final case class Multiply(exp1: Exp, exp2: Exp) extends Exp
final case class Divide(exp1: Exp, exp2: Exp) extends Exp
final case class Square(exp: Exp) extends Exp

sealed trait Exp
val evaluate: Exp => Double =

sealed trait Exp
val evaluate: Exp => Double = {
case IntValue(v) => v.toDouble
case DecValue(v) => v
case Sum(exp1, exp2) => evaluate(exp1) + evaluate(exp2)
case Multiply(exp1, exp2) => evaluate(exp1) * evaluate(exp2)
case Square(exp) =>
val v = evaluate(exp)
v * v
case Divide(exp1, exp2) => evaluate(exp1) / evaluate(exp2)
}

sealed trait Exp
val mkString: Exp => String = {
case IntValue(v) => v.toString
case DecValue(v) => v.toString
case Sum(exp1, exp2) => s"( ${mkStr(exp1)} + ${mkStr(exp2)})"
case Multiply(exp1, exp2) => s"( ${mkStr(exp1)} * ${mkStr(exp2)})"
case Square(exp) => s"(${mkStr(exp)})^2"
case Divide(exp1, exp2) => s"( ${mkStr(exp1)} / ${mkStr(exp2)})"
}

sealed trait Exp
val optimize: Exp => Exp = {
case Multiply(exp1, exp2)
if(exp1 == exp2) => Square(optimize(exp1))

sealed trait Exp
case IntValue(v) => IntValue(v)
case DecValue(v) => DecValue(v)
case Sum(exp1, exp2) => Sum(optimize(exp1), optimize(exp2))
case Multiply(exp1, exp2) => Multiply(optimize(exp1), optimize(exp2))
case Square(exp) => Square(optimize(exp))
case Divide(exp1, exp2) => Divide(optimize(exp1), optimize(exp2))
}

sealed trait Exp
case Multiply(exp1, exp2) => Multiply(exp1, optimize(exp2))
}

sealed trait Exp
case IntValue(v) => optimize(IntValue(v))
case DecValue(v) => optimize(DecValue(v))
}

val evaluate: Exp => Double = {
case Sum(exp1, exp2) =>
evaluate(exp1) + evaluate(exp2)
case Multiply(exp1, exp2) =>
evaluate(exp1) * evaluate(exp2)
case Square(exp) =>
val v = evaluate(exp)
v * v
case Divide(exp1, exp2) =>
evaluate(exp1) / evaluate(exp2)
}
val exp = Multiply(
Sum(IntValue(10),
DecValue(2.5)),
Divide(DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
Multiply
Sum Divide
Int(10) Dec(2.5) Dec(5.2) Sum
Int(10) Int(5)

val mkString: Exp => String = {
case Sum(exp1, exp2) =>
s"(${mkStr(exp1)} + ${mkStr(exp2)})"
case Multiply(exp1, exp2) =>
s"(${mkStr(exp1)} * ${mkStr(exp2)})"
case Square(exp) =>
s"(${mkStr(exp)})^2"
case Divide(exp1, exp2) =>
s"( ${mkStr(exp1)} / ${mkStr(exp2)})"
} val exp = Multiply(
Sum(IntValue(10),
DecValue(2.5)),
Divide(DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
Multiply
Sum Divide
Int(10) Dec(2.5) Dec(5.2) Sum
Int(10) Int(5)

sealed trait Exp

sealed trait Exp
sealed trait Exp[A]
final case class IntValue[A](v: Int) extends Exp[A]
final case class DecValue[A](v: Double) extends Exp[A]
final case class Sum[A](exp1: A, exp2: A) extends Exp[A]
final case class Multiply[A](exp1: A, exp2: A) extends Exp[A]
final case class Divide[A](exp1: A, exp2: A) extends Exp[A]
final case class Square[A](exp: A) extends Exp[A]

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp1: Exp[?] =
Sum[?](IntValue[?](10),
IntValue[?](5))
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp1: Exp[?] =
Sum[?](IntValue[Unit](10),
IntValue[Unit](5))
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp1: Exp[?] =
IntValue[Unit](5))
)
Exp[Unit]

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp1: Exp[?] =
Sum[Exp[Unit]](IntValue[Unit](10),
IntValue[Unit](5))
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp1: Exp[Exp[Unit]] =
IntValue[Unit](5))
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp2: Exp =
Divide(
DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
IntValue[Unit](5))
)
val exp2: Exp[?] =
Divide[?](
DecValue[?](5.2),
Sum[?](IntValue[?](10),
IntValue[?](5))
)
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp2: Exp =
Divide(
DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
IntValue[Unit](5))
)
val exp2: Exp[?] =
Divide[?](
DecValue[?](5.2),
IntValue[Unit](5))
)
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp2: Exp =
Divide(
DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
IntValue[Unit](5))
)
val exp2: Exp[?] =
Divide[?](
DecValue[Exp[Unit]](5.2),
IntValue[Unit](5))
)
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp2: Exp =
Divide(
DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
IntValue[Unit](5))
)
val exp2: Exp[?] =
Divide[Exp[Exp[Unit]]](
IntValue[Unit](5))
)
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp2: Exp =
Divide(
DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
IntValue[Unit](5))
)
val exp2: Exp[Exp[Exp[Unit]]] =
IntValue[Unit](5))
)
)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp2: Exp =
Divide(
DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
val exp3: Exp = from(input)
IntValue[Unit](5))
)
IntValue[Unit](5))
)
)
val exp3: Exp[?] = from(input)

sealed trait Exp[A]
val exp1: Exp =
Sum(IntValue(10),
IntValue(5))
)
val exp2: Exp =
Divide(
DecValue(5.2),
Sum(IntValue(10),
IntValue(5))
)
)
val exp3: Exp = from(input)
IntValue[Unit](5))
)
IntValue[Unit](5))
)
)
val exp3: Exp[Exp[Exp[Exp[Exp[Exp[Exp[Exp[Exp[Ex

Introducing:
fix point data
types!

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

Sum[Exp[Unit]](
IntValue[Unit](10),
IntValue[Unit](5)
)

Sum[Exp[Unit]](
Fix(IntValue[Unit](10)),
Fix(IntValue[Unit](5))
)

Sum[Exp[Unit]](
Fix(IntValue[Fix[Exp]](10)),
Fix(IntValue[Fix[Exp]](5))
)

Sum[Fix[Exp]](
)

Fix(Sum[Fix[Exp]](
))

val exp1: Fix[Exp] =
Fix(Sum[Fix[Exp]](
))

Fix(Sum[Fix[Exp]](
))
Sum[Exp[Unit]](
IntValue[Unit](10),
IntValue[Unit](5))
)
)

Fix(Sum[Fix[Exp]](
))
Sum[Exp[Unit]](
Fix(IntValue[Fix[Exp]](5)))
)
)

Fix(Sum[Fix[Exp]](
))
Sum[Fix[Exp]](
)
)

Fix(Sum[Fix[Exp]](
))
Fix(DecValue[Fix[Exp]](5.2)),
Sum[Fix[Exp]](
)
)

Fix(Sum[Fix[Exp]](
))
Fix(Sum[Fix[Exp]](
))
)

Fix(Sum[Fix[Exp]](
))
Fix(Divide[Fix[Exp]](
Fix(Sum[Fix[Exp]](
))
))

Fix(Sum(
Fix(IntValue(10)),
Fix(IntValue(5))
))
Fix(Divide(
Fix(DecValue(5.2)),
Fix(Sum(
Fix(IntValue(10)),
Fix(IntValue(5))
))
))

Fix(Sum(
Fix(IntValue(10)),
Fix(IntValue(5))
))
Fix(Divide(
Fix(DecValue(5.2)),
Fix(Sum(
Fix(IntValue(10)),
Fix(IntValue(5))
))
))
val exp3: Fix[Exp] = from(input)

Need something
that will
traverse the
structure…

Functor 101
trait Functor[F[_]] {
def map[A, B](fa: F[A])(f: A => B): F[B]
}

Functor 101
}
def foo[A[_], T](a: A[T])

Functor 101
}
def foo[A[_], T](a: A[T])(trans: T => Int)

Functor 101
}
def foo[A[_], T](a: A[T])(trans: T => Int): A[Int] = ???

Functor 101
}
def foo[A[_] : Functor, T](a: A[T])(trans: T => Int): A[Int] = ???

Functor 101
}
def foo[A[_] : Functor, T](a: A[T])(trans: T => Int): A[Int] = a.map(trans)

Functor 101
}
case class Container[T](t: T)
val r: Container[Int] =
foo[Container, String](Container("bar"))(str => str.length)

Functor 101
}
implicit val functor: Functor[Container] = new Functor[Container] {
def map[A, B](c: Container[A])(f: A => B): Container[B] = Container(f(c.t))
}
case class Container[T](t: T)
val r: Container[Int] =
foo[Container, String](Container("bar"))(str => str.length)

sealed trait Exp
implicit val functor: Functor[Exp] = new Functor[Exp] {
def map[A, B](exp: Exp[A])(f: A => B): Exp[B] =

sealed trait Exp
implicit val functor: Functor[Exp] = new Functor[Exp] {
def map[A, B](exp: Exp[A])(f: A => B): Exp[B] = exp match {
case Sum(a1, a2) => Sum(f(a1), f(a2))
case Multiply(a1, a2) => Multiply(f(a1), f(a2))
case Divide(a1, a2) => Divide(f(a1), f(a2))
case Square(a) => Square(f(a))
}
}

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

val evaluate: Algebra[Exp, Double] = {
case Sum(a1, a2) => a1 + a2
case Multiply(a1, a2) => a1 * a2
case Square(a) => a * a
case Divide(a1, a2) => a1 / a2
}

val evaluate: Algebra[Exp, Double] = {
}
val mkStr: Algebra[Exp, String] = {
case Sum(a1, a2) => s"($a1 + $a2)"
case Multiply(a1, a2) => s"($a1 + $a2)"
case Square(a) => s"($a)^2"
case Divide(a1, a2) => s"($a1 + $a2)"
}

val evaluate: Algebra[Exp, Double] = { // Exp[Double] => Double
}

}
val exp2: Fix[Exp] = Fix(Divide(
Fix(DecValue(5.2)),
Fix(Sum(
Fix(IntValue(10)),
Fix(IntValue(5))
))
))

}
Fix(DecValue(5.2)),
Fix(Sum(
Fix(IntValue(10)),
Fix(IntValue(5))
))
))
> exp2.cata(evaluate)
0.3466666666666667

val mkStr: Algebra[Exp, String] = { // Exp[Double] => Double
case Sum(a1, a2) => s"($a1 + $a2)"
}

case Sum(a1, a2) => s"($a1 + $a2)"
}
Fix(DecValue(5.2)),
Fix(Sum(
Fix(IntValue(10)),
Fix(IntValue(5))
))
))

case Sum(a1, a2) => s"($a1 + $a2)"
}
Fix(DecValue(5.2)),
Fix(Sum(
Fix(IntValue(10)),
Fix(IntValue(5))
))
))
> exp2.cata(mkStr)
(5.2 + (10 + 5))

}

}
val optimize: Algebra[Exp, Fix[Exp]] = { // Exp[Fix[Exp]] => Fix[Exp]
case Multiply(Fix(a1), Fix(a2)) if(a1 == a2) => Fix(Square(Fix(a1)))
case other => Fix(other)
}

}

}
val aTimesAExp: Fix[Exp] =
Fix(Multiply(
Fix(Sum(
)),
Fix(Sum(
))
))

}
val aTimesAExp: Fix[Exp] =
Fix(Multiply(
Fix(Sum(
)),
Fix(Sum(
))
))
> aTimesAExp.cata(optimize)
Fix(Square(Fix(Sum(Fix(IntValue(10)),Fix(IntValue(20))))))

Anamorphism
●
●
●
●
●

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

val divisors: Coalgebra[Exp, Int] = {
case n if(n % 2 == 0 && n != 2) => Multiply(2, n / 2)
case n => IntValue(n)
}

}
> 12.ana[Fix, Exp](divisors)

}
> 12.ana[Fix, Exp](divisors)
Fix(Multiply(Fix(IntValue(2)),Fix(Multiply(Fix(IntValue(2)),Fix(Multiply(Fix(IntVal
ue(2)),Fix(IntValue(7))))))))

val divisors: Coalgebra[Exp, Int] = { … } // Double => Exp[Double]
val evaluate: Algebra[Exp, Double] = { … } // Exp[Double] => Double

describe("divisors") {
it("once evaluated will give initial value") {
forAll(positiveInt) { n =>
n.ana(divisiors).cata(evaluate) shouldEqual(n)
}
}

describe("divisors") {
it("once evaluated will give initial value") {
forAll(positiveInt) { n =>
n.hylo(evaluate, divisors) shouldEqual(n)
}
}

To sum it up
●
●
●
○
○

To sum it up
●
●
●
○
○
●

To sum it up
●
●
●
○
○
●
●

To sum it up
●
●
●
○
○
●
●
●

Pawel Szulc
@rabbitonweb
paul.szulc@gmail.com

Pawel Szulc
@rabbitonweb
paul.szulc@gmail.com
http://rabbitonweb.com

Going bananas with recursion schemes for expression evaluation

Recommended

Recommended

More Related Content

What's hot

What's hot (17)

Viewers also liked

Viewers also liked (20)

Similar to Going bananas with recursion schemes for expression evaluation

Similar to Going bananas with recursion schemes for expression evaluation (20)

More from Pawel Szulc

More from Pawel Szulc (19)

Recently uploaded

Recently uploaded (20)

Going bananas with recursion schemes for expression evaluation