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

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


当前回答

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所提到的:大多数过程式语言都有静态类型。

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

其他答案对此提供了相当简洁的答案,但没有一个重要的事实:你不需要用任何实用语言以这种令人费解的方式实现定点组合子,这样做没有任何实际目的(除了“看,我知道y组合子是什么”)。这是一个重要的理论概念,但没有什么实际价值。

Y-Combinator是通量电容器的另一个名称。

Y-combinator是一个“函数”(一个作用于其他函数的函数),当你不能从内部引用函数时,它可以实现递归。在计算机科学理论中,它概括了递归,抽象了递归的实现,从而将递归与函数的实际工作分离开来。递归函数不需要编译时名称的好处是一种额外的好处。=)

这适用于支持lambda函数的语言。lambdas基于表达式的特性通常意味着它们不能通过名称引用自己。通过声明变量,引用它,然后赋值给它,来完成自引用循环,是很脆弱的。可以复制lambda变量,并重新分配原始变量,这将破坏自引用。

y组合子在静态类型语言(过程性语言通常如此)中实现起来很麻烦,而且经常使用起来也很麻烦,因为通常类型限制要求在编译时知道函数的参数数量。这意味着必须为需要使用的任何参数count编写y-combinator。

下面是一个在c#中如何使用和工作的Y-Combinator的例子。

使用y组合子涉及到一种构造递归函数的“不寻常”方式。首先,你必须把你的函数写成一段代码,调用一个已经存在的函数,而不是它自己:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

然后将其转换为一个函数,该函数接受一个要调用的函数,并返回一个这样做的函数。这被称为函数,因为它接受一个函数,并对其执行一个操作,该操作产生另一个函数。

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

现在你有了一个函数,它接受一个函数,并返回另一个函数,它看起来像一个阶乘,但它不是调用它自己,而是调用传递给外部函数的参数。怎么把它变成阶乘呢?将内部函数传递给自身。Y-Combinator就是这样做的,它是一个具有永久名称的函数,可以引入递归。

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

不是阶乘调用自身,而是阶乘调用阶乘生成器(由对Y-Combinator的递归调用返回)。根据t的当前值,从生成器返回的函数会再次调用生成器,用t - 1,或者直接返回1,终止递归。

它是复杂而神秘的,但在运行时,它的工作关键是“延迟执行”,并将递归分解为跨越两个函数。内部的F作为参数传递,仅在必要时才在下一次迭代中调用。

为了帮助自己掌握Y-Combinator,我在Clojure和Scheme中都写了一份关于Y-Combinator的“傻瓜指南”。他们受到了《小阴谋家》的影响

在方案: https://gist.github.com/z5h/238891

Clojure: https://gist.github.com/z5h/5102747

这两个教程都是代码中穿插的注释,应该剪切和粘贴到您最喜欢的编辑器。