使用 Kotlin 实现 Y 组合子（Y-Combinator）

---

《Kotlin极简教程》正式上架：

点击这里 > 去京东商城购买阅读

点击这里 > 去天猫商城购买阅读

非常感谢您亲爱的读者，大家请多支持！！！有任何问题，欢迎随时与我交流~

---

我们可以使用 Kotlin FP (Lambda, function) 写一个 Y-combinator 函数吗?

Y = λf.(λx.f (x x)) (λx.f (x x))

我们知道，In JS:

function Y(f) {
    return (function (g) {
        return g(g);
    })(function (g) {
        return f(function (x) {
            return g(g)(x);
        });
    });
}

var fact = Y(function (rec) {
    return function (n) {
        return n == 0 ? 1 : n * rec(n - 1);
    };
});

In Coffee:

coffee> Y = (f) -> ((x) -> (x x)) ((x) -> (f ((y) -> ((x x) y))))
[Function]

coffee> fact = Y (f)  ->(n) -> if n==0 then 1 else n*f(n-1)
[Function]

coffee> fact(10)
3628800

在动态类型语言中，Y 组合子（Y-Combinator）实现起来很方便。

使用 Java 的接口和类型转换我们也可以实现

public class YCombinator {

    public static Lambda<Lambda> yCombinator2(final Lambda<Lambda> f) {
        return ((Lambda<Lambda>)(Object input) -> {
            final Lambda<Lambda> u = (Lambda<Lambda>)input;
            return u.call(u);
        }).call(
            ((Lambda<Lambda>)(Object input) -> {
                final Lambda<Lambda> v = (Lambda<Lambda>)input;
                return f.call((Lambda<Object>)(Object p) -> {
                    return v.call(v).call(p);
                });
            })
        );

    }

    public static void main(String[] args) {
        Lambda<Lambda> y = yCombinator(
            (Lambda<Lambda>)(Object input) -> {
                Lambda<Integer> fab = (Lambda<Integer>)input;
                return (Lambda<Integer>)(Object p) -> {
                    Integer n = Integer.parseInt(p.toString());
                    if (n < 2) {
                        return Integer.valueOf(1);
                    } else {
                        return n * fab.call(n - 1);
                    }
                };
            });

        System.out.println(y2.call(10));//输出： 3628800
    }

    interface Lambda<E> {
        E call(Object input);
    }

}

类似的使用 Kotlin 的 OOP 编程范式 Y 组合子 实现就是：

object YCombinatorKt {

    fun yCombinator(f: Lambda<Lambda<*>>): Lambda<Lambda<*>> {

        return object : Lambda<Lambda<*>> {

            override fun call(n: Any): Lambda<*> {
                val u = n as Lambda<Lambda<*>>
                return u.call(u)
            }
        }.call(object : Lambda<Lambda<*>> {

            override fun call(n: Any): Lambda<*> {
                val x = n as Lambda<Lambda<*>>

                return f.call(object : Lambda<Any> {
                    override fun call(n: Any): Any {
                        return x.call(x).call(n)!!
                    }
                })
            }

        }) as Lambda<Lambda<*>>
    }

    @JvmStatic fun main(args: Array<String>) {

        val y = yCombinator(object : Lambda<Lambda<*>> {

            override fun call(n: Any): Lambda<*> {
                val fab = n as Lambda<Int>

                return object : Lambda<Int> {

                    override fun call(n: Any): Int {
                        val n = Integer.parseInt(n.toString())
                        if (n < 2) {
                            return Integer.valueOf(1)
                        } else {
                            return n * fab.call(n - 1)
                        }
                    }
                }
            }
        })

        println(y.call(10)) //输出： 3628800
    }

    interface Lambda<E> {
        fun call(n: Any): E
    }
}

当然，对于函数式编程也完全支持的 Kotlin 也有 FP 风格的Y 组合子实现：

/**
 * Created by jack on 2017/7/9.
 *
 * lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
 *
 * FP YCombinator
 */

// 为了方便易懂，使用 X 用做函数 (X)->Int 的别名
typealias X = (Int) -> Int
// G 递归引用 G 自己
interface G : Function1<G, X>
// create a fun G from lazy blocking
fun G(block: (G) -> X) = object : G {
    // 调用函数自身 `block(g)` like as `g(g)`
    override fun invoke(g: G) = block(g)
}

typealias F = Function1<X, X>
fun Y(f: F) = (fun(g: G) = g(g))(G { g -> f({ x -> g(g)(x) }) })

val fact = Y {
    rec ->
    {
        n ->
        if (n == 0) 1 else n * rec(n - 1)
    }
}
val fib = Y { f ->
    {
        n ->
        if (n == 1 || n == 2) 1 else f(n - 1) + f(n - 2)

    }
}


fun main(args: Array<String>) {
    println(fact(10))
    println(fib(10))

    for (i in 1..10) {
        println("$i!= ${fact(i)}")
    }

    for (i in 1..10) {
        println("fib($i) = ${fib(i)}")
    }
}

其中，在接口 G 继承了Function1<G, X>接口：

interface G : Function1<G, X>

这个Function1 接口是继承自kotlin.Function 接口：

public interface Function<out R>

Function1 有一个抽象算子函数invoke ， 用来调用入参 p1 ：

public interface Function1<in P1, out R> : kotlin.Function<R> {
    public abstract operator fun invoke(p1: P1): R
}

我们定义的 G 函数，入参是block函数 (G) -> X , block函数的入参又是 G 类型，通过 invoke 函数来实现 调用自身：

fun G(block: (G) -> X) = object : G {
    // 调用函数自身 `block(g)` like as `g(g)`
    override fun invoke(g: G) = block(g)
}

这样，我们就可以实现一个 Y 组合子函数了：

typealias F = Function1<X, X>

fun Y(f: F) = (fun(g: G) = g(g))(G { g -> f({ x -> g(g)(x) }) })

我们通过 Y 组合子定义阶乘递归函数和 Fibonacci 数列函数：

val fact = Y {
    rec ->
    {
        n ->
        if (n == 0) 1 else n * rec(n - 1)
    }
}
val fib = Y { f ->
    {
        n ->
        if (n == 1 || n == 2) 1 else f(n - 1) + f(n - 2)

    }
}

测试代码：

fun main(args: Array<String>) {
    val square: X = { x -> x * x }
    println(square(9))

    println(fact(10))
    println(fib(10))

    for (i in 1..10) {
        println("$i!= ${fact(i)}")
    }

    for (i in 1..10) {
        println("fib($i) = ${fib(i)}")
    }
}

Github 源码工程： https://github.com/EasyKotlin/chapter8_fp