从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。

什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?


当前回答

我从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html中引用了这个,这是我几年前写的一个解释。

在本例中我将使用JavaScript,但许多其他语言也可以。

我们的目标是写出一个1的递归函数 变量只使用1变量的函数,没有 赋值,通过名称定义事物等(为什么这是我们的 目标是另一个问题,我们把它作为 我们所面临的挑战。)似乎不可能,是吧?作为 举个例子,让我们实现阶乘。

第一步是说我们可以很容易地做到这一点,如果我们 作弊了一点。使用二元函数和 我们至少可以避免使用 赋值来建立递归。

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

现在我们看看能不能少作弊。首先我们用 任务,但我们不需要。我们可以写成X和 Y内联。

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

但是我们用两个变量的函数来得到一个1的函数 变量。我们能解决这个问题吗?一个叫 Haskell Curry有一个巧妙的技巧,如果你有好的高阶 那么你只需要一个变量的函数。的 证明是你可以从函数2(或更多) 一般情况下)变量以1变量为纯粹 像这样的机械文本转换:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

在那里……完全一样。(这个技巧叫做 “模仿”它的发明者。Haskell也是一种语言 以哈斯克尔·库里命名。把它归为无用的琐事。) 现在只要把这个变换应用到任何地方,我们就得到 我们的最终版本。

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

尽管试一试。Alert()返回,将其绑定到一个按钮,等等。 该代码不使用,递归地计算阶乘 2变量的赋值、声明或函数。(但 试图追踪它是如何工作的可能会让你头晕目眩。 递过来,没有推导,只是稍微重新格式化了一下 会导致代码令人困惑。)

可以将递归定义阶乘的4行替换为 任何你想要的递归函数。

其他回答

我认为回答这个问题的最好方法是选择一种语言,比如JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

现在重写它,使它不使用函数内部的函数名,但仍然递归地调用它。

函数名factorial唯一应该看到的地方是在调用位置。

提示:不能使用函数名,但可以使用参数名。

解决这个问题。不要去查。一旦你解决了它,你就会明白y组合子解决了什么问题。

y组合子实现匿名递归。所以与其

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

你可以这样做

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

当然,y-combinator只适用于按名字命名的语言。如果你想在任何正常的值调用语言中使用它,那么你将需要相关的z-combinator (y-combinator将发散/无限循环)。

以下是对尼古拉斯·曼库索(Nicholas Mancuso)在回答中提到的文章(完全值得一读)中提到的原始问题的回答,以及其他答案:

什么是y组合子?

y组合子是一个“函数”(或高阶函数——一个作用于其他函数的函数),它接受一个参数,这是一个非递归的函数,并返回该函数的一个递归版本。


有点递归=),但更深入的定义:

一个组合子-就是一个没有自由变量的lambda表达式。 自由变量-是一个变量,不是一个约束变量。 绑定变量—包含在lambda表达式体中的变量,该变量名作为其参数之一。

另一种思考方式是,combinator是这样一个lambda表达式,在其中,你可以在任何地方用它的定义替换一个组合子的名称,并且一切都仍然有效(如果combinator在lambda体中包含对自身的引用,你将进入一个无限循环)。

y组合子是一个定点组合子。

函数的不动点是函数定义域中映射到函数自身的一个元素。 也就是说,如果f(c) = c, c是函数f(x)的一个不动点 这意味着f(f(…f(c)…))= fn(c) = c

组合符是如何工作的?

下面的例子假设强+动态类型:

惰性(正规阶)y组合子: 此定义适用于具有lazy(也称为deferred, call-by-need)求值的语言——该求值策略将表达式的求值延迟到需要它的值时。

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

这意味着,对于给定的函数f(它是非递归函数),可以通过计算λx得到对应的递归函数。F (x x)然后把这个表达式应用到自身上。

严格(应用阶)y组合子: 这个定义适用于具有严格求值策略(也包括热切求值和贪婪求值策略)的语言,在这种策略中,表达式一旦绑定到变量就会被求值。

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

它本质上和lazy一样,只是有一个额外的λ包装器来延迟lambda的体计算。我问了另一个问题,和这个话题有点相关。

它们有什么用?

借用Chris Ammerman的回答:Y-combinator泛化递归,抽象其实现,从而将其与函数的实际工作分离。

尽管Y-combinator有一些实际应用,但它主要是一个理论概念,理解它将扩展你的整体视野,并有可能提高你的分析和开发技能。

它们在过程语言中有用吗?

正如Mike Vanier所说:在许多静态类型的语言中都可以定义Y组合子,但是(至少在我看到的例子中)这样的定义通常需要一些不明显的类型技巧,因为Y组合子本身没有直接的静态类型。这超出了本文的范围,所以我不再进一步提及

正如Chris Ammerman所提到的:大多数过程式语言都有静态类型。

所以这个问题的答案是,不是真的。

如果你准备好长篇大论,Mike Vanier有一个很好的解释。长话短说,它允许您在一种不一定支持递归的语言中实现递归。

不动点组合子(或不动点运算符)是一种高阶函数,用于计算其他函数的一个不动点。此操作与编程语言理论相关,因为它允许以重写规则的形式实现递归,而不需要语言的运行时引擎的显式支持。(src维基百科)