Y Combinator

05-14-2015

由于匿名函数(通常成为lambda函数但是跟lambda calculus不同)在递归时无法获得函数名，从而导致一些问题，而Y Combinator能很好地解决这个问题。利用不动点的原理，可以利用一般的函数来辅助得到匿名函数的递归形式，从而间接调用无法表达的真正的匿名函数。下面以一个阶乘的递归来说明。

#Python版本，后面会加上C++版本
#F(f) = f
def F(f,n):
    return 1 if n==0 else n*f(n-1)
#或者用lambda
#F = lambda f,n: 1 if n==0 else n*f(n-1)
#Y不能用lambda，因为Y会调用自己

#Y(F) = f = F(f) = F(Y(F))
def Y(F):
    return lambda n: F(Y(F),n)
a = Y(F)
# 6
print a(3)

一些解释：

  • F是伪递归函数，将真正的我们假设的匿名函数作为参数，有性质 F(f)=f.
  • 好了以上是我们的已知条件，为了得到f的间接表达式，我们引入Y函数 使得Y(F) = f
  • 所以有Y(F) = f = F(f) = F(Y(F)) （最终的目标是要用YF的组合表示f），所以很容易就得到了Y(F)的函数表达式为F(Y(F))，而Y不是匿名函数，所以能自身调用(其实感觉这东西没想象中那么玄乎～)，上面的代码也就比较好理解了。我们假设的函数只有一个额外参数n，这完全可以自己添加其他参数，只需稍微修改Y中F的调用。

最后附上一段C++的实现代码：

//需要C++11支持
#include <iostream>
#include <functional>
//F(f) = f
int 
F(std::function<int(int)> f, int n)
{
    return n==0 ? 1 : n*f(n-1);
}
//或者
//auto F1 = [](std::function<int(int)> f, int n) {
//    return n==0 ? 1 : n*f(n-1);
//};


//Y(F) = f = F(f) = F(Y(F))
std::function<int(int)>
Y(std::function<int(std::function<int(int)>,int)> F)
{
    return std::bind(F, std::bind(Y,F), std::placeholders::_1);
}

int main(int argc, char *argv[])
{
    auto f = Y(F);
    std::cout << f(3) << std::endl; //6
    return 0;
}
comments powered by Disqus