我无法理解Y-Combinator，所以我试图实现它，最后得到了一些较短的工作。这怎么可能？ [英] I couldn't understand the Y-Combinator, so I tried to implement it and ended up with something shorter, which worked. How is that possible?

问题描述

我无法理解Y组合器，因此我试图实现一个无需本地实现即可启用递归的函数。经过一番思考，我最终得出了这个结论：

  Y =λx。（λv。（xx）v）
  

这比实际的短：

  Y =λf。（λx.f（xx））（λx.f（xx））
  

令我惊讶的是，他工作。一些例子：
$ b $ pre $ code $ //
Y = function（x）{
return function（v） {
return x（x，v）;
};
};
sum = Y（function（f，n）{
return n == 0？0：n + f（f，n - 1）;
}）;
sum（4）;

; Scheme
（define Y（lambda（x）（lambda（v）（xxv））））
（define sum（Y
（lambda（fn）
（if（equal

（+ n（ff（ - n 1）））））））
（sum 4）
pre>

这两个片段输出10（总计从0到4）与预期一致。

这是什么，为什么它更短，为什么我们更喜欢更长的版本？

解决方案

短的原因是您实现的是而不是 Y组合器。它是在实际的Y组合器和有时被称为U组合器的东西之间的东西。要成为一个合适的Y组合器，这应该工作：

$ $ p $ $ $ $ $ $ $（定义和
（Y（lambda（f）
（lambda（v）（if（equal？n 0）0（+ n（f（ - n 1））））））））

  sum = Y（function（f）{$ p 
 
 
 return function（n）{
 return n == 0？0：n + f（n-1）; 
};}）; 
  

如果您按照使 的方式工作，你会发现有一件事会让它变长的是，你需要将重复的 f 事物移到Y中，接下来的事情会让它变得更长时间是当你结束时保护函数中的 xx 自我应用程序，因为这些语言是严格的。

I couldn't understand the Y-combinator, so I tried to implement a function that enabled recursion without native implementation. After some thinking, I ended up with this:

Y = λx.(λv.(x x) v)

Which is shorter than the actual one:

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

And, for my surprise, worked. Some examples:

// JavaScript
Y = function(x){
  return function(v){
    return x(x, v);
  };
};
sum = Y(function(f, n){
  return n == 0 ? 0 : n + f(f, n - 1);
});
sum(4);

; Scheme
(define Y (lambda (x) (lambda (v) (x x v))))
(define sum (Y 
    (lambda (f n) 
        (if (equal? n 0) 
            0 
            (+ n (f f (- n 1)))))))
(sum 4)

Both snippets output 10 (summation from 0 to 4) as expected.

What is this, why it is shorter and why we prefer the longer version?

解决方案

The reason it is shorter is that what you implemented is not the Y combinator. It's something that is between the actual Y combinator, and something that is sometimes known as a U combinator. To be a proper Y combinator, this should work:

(define sum
  (Y (lambda (f)
       (lambda (v) (if (equal? n 0) 0 (+ n (f (- n 1))))))))

or in Javascript:

sum = Y( function(f) { return function(n) {
  return n == 0 ? 0 : n + f(n-1);
};});

If you work your way to something that makes that work, you'll find that one thing that will make it longer is that you need to move the duplicated f thing into the Y, and the next thing that makes it even longer is when you end up protecting the x x self-application inside a function since these language are strict.

这篇关于我无法理解Y-Combinator，所以我试图实现它，最后得到了一些较短的工作。这怎么可能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！