link之家

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

相关文章推荐

怕考试的苹果 · 暗部论坛 - 百度· 1 年前 ·

鼻子大的红金鱼 · 权威发布 - 中华人民共和国最高人民法院· 2 年前 ·

不要命的自行车 · 仙源大揭秘 ...· 2 年前 ·

开朗的洋葱 · 真相在此！美国对华认知的21个谬误_新华报业网· 2 年前 ·

英姿勃勃的葡萄 · 多玩被判侵权赔偿爱奇艺52万 ...· 2 年前 ·

也许你我都难以理解，为什么有人对她痴迷疯狂，铭记在心中不说，还要刻在身上。她让人绞尽脑汁，也琢磨不定！她让人心力憔悴，又百般回味！她，看似平淡，却深藏玄机！她，貌不惊人，却天下无敌！她是谁？她就是...

本系列文章目录：

也许你我都难以理解，为什么有人对她痴迷疯狂，铭记在心中不说，还要刻在身上：

y_combinator

她让人绞尽脑汁，也琢磨不定！她让人心力憔悴，又百般回味！

她，看似平淡，却深藏玄机！她，貌不惊人，却天下无敌！

她是谁？她就是 Y 组合子 ： Y = λf.(λx.f (x x)) (λx.f (x x)) ，不动点组合子中最著名的一个。

小小开场抒情后，开始本文的内容，使用 c# 实现 Y 组合子。

本文继续使用上一篇文章中的类型假定，假定递归函数：

参数为 int；
返回值为 long。

实现 Y 组合子算法

Y 组合子 η-展开

Y 组合算子的定义：

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

Y = λg. h(h) 变换一步得 Y g = h(h)，再变换一次 Y(g) = h(h)，可以看出 h 的返回值即是 Y 的返回值。

前文中已确定 Y 返回值的类型为 Func<int, long>，所以 h 的返回值类型为 Func<int, long> 。

再来确定 h 的参数类型，h 调用自身 h(h)，因此 h 参数的类型就是 h 的类型， h 参数和 h 是同一类型，都是未确定的。

通过以下这个奇妙的委托，可以来表示自身调用有逻辑：

Func<Func<Func<int, long>, Func<int, long>>, Func<int, long>> Y = g => {
    SelfApplicable<Func<int, long>> h = x => n => g(x(x))(n);
    return h(h);
        public static Func<int, long> Y(Func<Func<int, long>, Func<int, long>> g) {
    SelfApplicable<Func<int, long>> h = x => n => g(x(x))(n);
    return h(h);
        delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> self);
static void Main(string[] args) {
    Func<Func<Func<int, long>, Func<int, long>>, Func<int, long>> Y = g => {
                SelfApplicable<Func<int, long>> h = x => n => g(x(x))(n);
        return h(h);
    Func<int, long> fact = Y(f => n => n == 0 ? 1 : n * f(n - 1));
    long result = fact(5);  // 结果为 120;
        public static class YCombitator {
    delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> self);
    public static Func<TInput, TResult> Fix<TInput, TResult>(Func<Func<TInput, TResult>, Func<TInput, TResult>> g) {
        SelfApplicable<Func<TInput, TResult>> h = x => n => g(x(x))(n);
        return h(h);
        var factorial = YCombitator.Fix<int, int>(f => n => n == 0 ? 1 : n * f(n - 1));
var result1 = factorial(5);   // 120
var fibonacci = YCombitator.Fix<int, int>(f => n => n < 2 ? n : f(n - 1) + f(n - 2));
var result2 = fibonacci(5);   // 5
            delegate T SelfApplicable<T>(SelfApplicable<T> self); 
  static void Main(string[] args)  {
     SelfApplicable<Func<Func<Func<int,int>, Func<int,int>>, Func<int,int>>> Y = y => f => x => f(y(y)(f))(x); 
     Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> Fix = Y(Y); 
     Func<Func<int,int>, Func<int,int>> F = fac => x => x == 0 ? 1 : x * fac(x-1); 
               Func<int,int> factorial = Fix(F);
               var result = factorial(5);   // 120 
  The Why of Y：http://www.dreamsongs.com/Files/WhyOfY.pdf 
  数学纹身：http://www.thedistractionnetwork.com/topics/math-and-science/math-tattoos/ 
  图形化 lambda 计算器：http://joerg.endrullis.de/lambdaCalculator.html 
    -------------------
思想火花，照亮世界