functional-programming - 什么是 Y 组合器？

Question

Y 组合器是一个来自事物“功能”方面的计算机科学概念。大多数程序员即使听说过组合器，也对组合器知之甚少。

• 什么是 Y 组合器？
• 组合器如何工作？
• 它们有什么用处？
• 它们在过程语言中有用吗？

Answer 1

Y 组合器是一种“函数式”(对其他函数进行操作的函数)，当您无法从函数内部引用该函数时，它可以启用递归。在计算机科学理论中，它概括了递归，抽象了其实现，从而将其与相关函数的实际工作分开。递归函数不需要编译时名称的好处是一种额外的好处。 =)

这适用于支持 lambda functions 的语言。 expression lambda 的基于 - 的性质通常意味着它们不能通过名称引用自身。通过声明变量、引用它，然后将 lambda 分配给它来完成自引用循环来解决这个问题是很脆弱的。 lambda 变量可以被复制，并重新分配原始变量，这会破坏自引用。

在 static-typed 中，Y 组合器的实现和使用都很麻烦。语言(procedural languages 通常是)，因为通常类型限制要求在编译时知道相关函数的参数数量。这意味着必须为需要使用的任何参数计数编写 y 组合器。

下面是 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 作为参数传递，仅在必要时在下一次迭代中调用。