Y Combinator-阿里云开发者社区

开发者社区> 开发与运维> 正文

Y Combinator

简介:

由于匿名函数(通常成为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;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章