aedans/Katalyst

Kotlin recursion schemes with Arrow

Katalyst

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.

Gradle

repositories {
    maven { url 'https://dl.bintray.com/aedans/maven/' }
}

dependencies {
    compile 'io.github.aedans:katalyst:$katalyst_version'
}

Features

• 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

Code sample

// 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
    }
}

Resources

Recursion Schemes, the original Haskell implementation.

Matryoshka, which much of Katalyst's code is based off of.