使用 Kotlin 实现 Y 组合子（Y

组合子（Y"/>

使用 Kotlin 实现 Y 组合子（Y

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

我们可以使用 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 源码工程：