Skip to content
Kotlin recursion schemes with Arrow
Kotlin
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
gradle Add gradle Nov 23, 2017
src Fix parameter order Apr 16, 2018
.gitignore
LICENSE Create LICENSE Nov 26, 2017
README.md
build.gradle
gradlew
gradlew.bat Add gradle Nov 23, 2017
settings.gradle Add gradle Nov 23, 2017

README.md

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.

Download

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.

You can’t perform that action at this time.