Created
February 15, 2017 13:29
-
-
Save EncodePanda/a26cd78720ca222ec27effd56cb5e99f to your computer and use it in GitHub Desktop.
Very simple ¬ generic implementation of cata, ana & hylo for Fix
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
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