Notice: Katalyst has been merged with Arrow to create arrow-recursion and is no longer being maintained. See The Arrow Website and The Arrow Recursion Docs instead.
Kotlin recursion schemes with Arrow.
repositories {
maven { url 'https://dl.bintray.com/aedans/maven/' }
}
dependencies {
compile 'io.github.aedans:katalyst:$katalyst_version'
}- Mu, Nu, and Fix data types
- Recursive, Corecursive, and Birecursive typeclasses
- Cata, ana, and hylo recursion schemes
- EnvT and CoEnv data types
- List and Nat defined using recursion schemes
- Kleisli recursion schemes
- Generalized recursion schemes
- Advanced recursion schemes (para, apo, histo, futu, etc.)
- Free and Cofree defined using recursion schemes
- Recursive and Corecursive instances for Free and Cofree
- Elgot recursion schemes
// Define an expression pattern type
@higherkind
sealed class ExprPattern<out A> : ExprPatternOf<A> {
class Int(val value: kotlin.Int) : ExprPattern<Nothing>()
class Neg<out A>(val expr: A) : ExprPattern<A>()
class Plus<out A>(val expr1: A, val expr2: A) : ExprPattern<A>()
companion object
}
// Create a Functor instance for the expression pattern
@instance(ExprPattern::class)
interface ExprPatternFunctorInstance : Functor<ForExprPattern> {
override fun <A, B> ExprPatternOf<A>.map(f: (A) -> B) = run {
val fix = fix()
when (fix) {
is ExprPattern.Int -> fix
is ExprPattern.Neg -> ExprPattern.Neg(f(fix.expr))
is ExprPattern.Plus -> ExprPattern.Plus(f(fix.expr1), f(fix.expr2))
}
}
}
// Expand the expression pattern with a recursive type
typealias Expr = FixOf<ForExprPattern>
// Define convenience functions for constructing expressions
fun int(i: Int) = Fix(ExprPattern.Int(i))
fun neg(e: Expr) = Fix(ExprPattern.Neg(Eval.now(e)))
fun plus(a: Expr, b: Expr) = Fix(ExprPattern.Plus(Eval.now(a), Eval.now(b)))
// Define an algebra to evaluate an expression
fun evalExprAlgebra() = Algebra<ForExprPattern, Eval<Int>> {
val fix = it.fix()
when (fix) {
is ExprPattern.Int -> Eval.now(fix.value)
is ExprPattern.Neg -> fix.expr.map { -it }
is ExprPattern.Plus -> Eval.monad().binding { fix.expr1.bind() + fix.expr2.bind() }.ev()
}
}
// Use recursion schemes to generically apply algebras
fun main(args: Array<String>) {
val expr = plus(plus(int(1), int(2)), neg(plus(int(3), int(4))))
Fix.recursive().run {
expr.cata(evalExprAlgebra(), ExprPattern.functor()) // -4
}
}Recursion Schemes, the original Haskell implementation.
Matryoshka, which much of Katalyst's code is based off of.