Skip to content

Instantly share code, notes, and snippets.

@EncodePanda
Created February 15, 2017 13:29
Show Gist options
  • Save EncodePanda/a26cd78720ca222ec27effd56cb5e99f to your computer and use it in GitHub Desktop.
Save EncodePanda/a26cd78720ca222ec27effd56cb5e99f to your computer and use it in GitHub Desktop.
Very simple &not generic implementation of cata, ana & hylo for Fix
package rss
import scalaz._, Scalaz._
case class Fix[F[_]](unfix: F[Fix[F]])
object Fix {
type Algebra[F[_], A] = F[A] => A
type Coalgebra[F[_], A] = A => F[A]
def cata[F[_] : Functor, A](fix: Fix[F])(ψ: Algebra[F, A]): A = {
val func: Fix[F] => A = cata(_)(ψ)
val traverse: F[A] = fix.unfix.map(func)
ψ(traverse)
}
def ana[F[_]: Functor, A](a: A)(χ: Coalgebra[F, A]): Fix[F] = {
val func: A => Fix[F] = ana(_)(χ)
Fix(χ(a).map(func))
}
def hylo[F[_]: Functor, A, B](a: A)(χ: Coalgebra[F, A], ψ: Algebra[F, B]): B = {
val func: A => B = hylo(_)(χ, ψ)
val traverse: F[B] = χ(a).map(func)
ψ(traverse)
}
implicit class CataOps[F[_] : Functor, A](fix: Fix[F]) {
def cata(ψ: Algebra[F, A]): A = Fix.cata[F, A](fix)(ψ)
}
implicit class AnaOps[F[_] : Functor, A](a: A) {
def ana(ψ: Coalgebra[F, A]): Fix[F] = Fix.ana[F, A](a)(ψ)
}
implicit class HyloOps[F[_] : Functor, A, B](a: A) {
def hylo(χ: Coalgebra[F, A], ψ: Algebra[F, B]): B =
Fix.hylo[F, A, B](a)(χ, ψ)
}
}
object Sandbox extends App {
import Fix._
sealed trait Exp[A]
case class IntVal[A](i: Int) extends Exp[A]
case class Sum[A](exp1: A, exp2: A) extends Exp[A]
implicit def expFunctor: Functor[Exp] = new Functor[Exp] {
def map[A, B](fa: Exp[A])(f: A => B): Exp[B] = fa match {
case Sum(e1, e2) => Sum(f(e1), f(e2))
case IntVal(i) => IntVal(i)
}
}
def evaluate: Algebra[Exp, Int] = {
case Sum(i1, i2) => i1 + i2
case IntVal(i) => i
}
def mkStr: Algebra[Exp, String] = {
case Sum(i1, i2) => s"$i1 + $i2"
case IntVal(i) => s"$i"
}
val exp: Fix[Exp] = Fix(Sum(
Fix(IntVal(10)),
Fix(IntVal(20))
))
val exp2: Fix[Exp] = Fix(Sum(exp, exp))
println(exp2.cata(evaluate))
def explode: Coalgebra[Exp, Int] = {
case n if (n > 2) => Sum(2, n - 2)
case n => IntVal(n)
}
println(5.ana(explode))
println(6.ana(explode))
println(5.ana(explode).cata(mkStr))
println(5.hylo(explode, mkStr))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment