Church numerals Kotlin

church.kt

/**
 * Definition of Church numerals
 *
 * See: https://en.wikipedia.org/wiki/Church_encoding#Church_numerals
 */
typealias Church<T> = ((T) -> T) -> ((T) -> T)

fun <T> zero(f: (T) -> T): (T) -> T = { x -> x }
fun <T> succ(n: Church<T>): Church<T> = { f -> { x -> f(n(f)(x)) } }
fun <T> mult(n: Church<T>, m: Church<T>): Church<T> = { x -> m(n(x)) }

// direct definition of add without using succ
fun <T> add(c1: Church<T>, c2: Church<T>): Church<T> = { f -> { x -> c1(f)(c2(f)(x)) } }

// using succ, this is a little ugly in kotlin since the type of the first numeral needs to be a Church<Church>
// that said, type inference is good enough to make this work naturally when using generic functions
fun <T> addSucc(n: Church<Church<T>>, m: Church<T>): Church<T> = n(::succ)(m)

// Operators overloading!
operator fun <T> Church<T>.times(other: Church<T>): Church<T> = mult(this, other)
operator fun <T> Church<T>.plus(other: Church<T>): Church<T> = add(this, other)
operator fun <T> Church<T>.unaryPlus(): Church<T> = succ(this)


// Helpers
// throws stack overflow
fun <T> intToChurch(i: Int): Church<T> = (1..i).fold(::zero, { acc, _ -> succ(acc)})

/**
 * Prints a church numeral by turning it into an int.
 */
@Suppress("UNCHECKED_CAST")
fun <T> printChurch(church: Church<T>) {
    fun plusOne(i: Int): Int = i + 1

    // to church int
    println("Church ${(church as Church<Int>)(::plusOne)(0)}")
}


fun main(args: Array<String>) {
    printChurch<Any>(intToChurch(10000))

    // Limitation: can't assign generic function to a val without supplying a type
    // for example: val one = succ(::zero) won't compile
    val one: Church<Int> = succ(::zero)
    // we *can* define one as a function, but we have to put in a bunch of type info
    fun <T> one(f: (T) -> T): (T) -> T = succ<T>(::zero)(f)

    val two: Church<Int> = succ(succ(::zero))
    val three: Church<Int> = +two // overloading
    printChurch(two + three) // prints 5

    // adding using the successor function, type inference makes the first ::one a Church<Church<Any>>
    printChurch<Any>(addSucc(::one, succ(succ(::one)))) // prints 4

    // intToChurch can cause a stack overflow, but we can generate large numerals with our arithmetic
    printChurch<Any>(add(mult(intToChurch(1000), intToChurch(1000)), intToChurch(100)))

    // with operator overloading (needs a type hint)
    printChurch(intToChurch<Any>(1000) * intToChurch(1000) + intToChurch(100))
}