什么是Y组合?[关闭]

如果你已经准备好长期阅读, Mike Vanier has a great explanation . 长话短说,它允许您在不一定支持递归的语言中实现递归。

Y组合器是一个“函数”(在其他函数上操作的函数),当您不能从内部引用函数时,它启用递归。在计算机科学理论中 推广递归 抽象其实现,从而将其与相关函数的实际工作分离。递归函数不需要编译时名称的好处有点额外。=)

这适用于支持的语言 lambda functions . 这个 expression -羔羊的本源性通常意味着它们不能用名字来称呼自己。通过声明变量、引用变量、然后为其分配lambda来完成自引用循环来解决这个问题是脆弱的。可以复制lambda变量,并重新分配原始变量,这会中断自引用。

Y组合器在 static-typed 语言(其中 procedural languages 通常是),因为通常类型限制要求在编译时知道所讨论函数的参数数量。这意味着必须为需要使用的任何参数计数编写一个Y组合器。

下面是一个如何使用和工作的Y组合器的例子,在C。

使用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组合器通过成为一个具有永久名称的函数来实现这一点,该函数可以引入递归。

// 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.
}

与factorial调用本身不同,factorial调用factorial生成器(通过递归调用y-combinator返回)。根据t的当前值,从生成器返回的函数将使用t-1再次调用生成器,或者只返回1,终止递归。

它既复杂又神秘,但在运行时都会被淘汰,其工作的关键是“延迟执行”,以及将递归分解为跨两个函数。内部f是 作为参数传递 ,在下一个迭代中调用, 仅在必要时 .

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

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

我们的目标是能够编写1的递归函数 变量仅使用1个变量和no的函数 任务、按名称定义事物等(为什么这是我们的 目标是另一个问题,让我们把它作为 我们面临的挑战。)似乎不可能,嗯?AS 例如,让我们实现阶乘。

第一步是说如果我们 有点作弊。使用2个变量的函数和 我们至少可以避免使用 用于设置递归的赋值。

// 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的函数 变量。我们能修好吗?好吧,一个聪明人 哈斯克尔咖喱有一个巧妙的技巧,如果你有好的更高的订单 函数,那么您只需要1个变量的函数。这个 证明您可以从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个变量的赋值、声明或函数。(但是 试图追踪它是如何工作的,很可能会让你头晕目眩。 在不进行推导的情况下,只需稍微重新格式化即可。 将导致代码被混淆。)

可以将递归定义factorial的4行替换为 您想要的任何其他递归函数。

我想知道从地上建这个有没有用。让我们看看。下面是一个基本的递归阶乘函数:

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

让我们重构并创建一个名为 fact 返回匿名阶乘计算函数,而不是执行计算本身:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

这有点奇怪,但没什么问题。我们只是在每一步生成一个新的阶乘函数。

这个阶段的递归仍然相当明确。这个 事实 函数需要知道它自己的名称。让我们参数化递归调用:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

很好,但是 recurser 还需要知道自己的名字。我们也将其参数化:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

现在,而不是打电话 recurser(recurser) 直接,让我们创建一个返回其结果的包装函数:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

我们现在可以摆脱 递归器 总而言之,它只是y内部函数的一个参数,可以用函数本身替换:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

唯一仍被引用的外部名称是 事实 但现在应该很清楚,这也很容易参数化,从而创建完整的通用解决方案:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y(function(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
});

上面的大多数答案都描述了Y组合器 是 但不是什么 对于 .

Fixed point combinators 用来表示 lambda calculus 是 turing complete . 这是计算理论中的一个重要结果,为理论计算提供了理论基础。 functional programming .

研究固定点组合器也帮助我真正理解函数编程。不过,在实际的编程中,我从未发现它们有任何用处。

Y型组合器 JavaScript :

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

编辑 : 我从代码方面学到了很多东西,但是如果没有背景知识,这个有点难以接受——抱歉。有了其他答案提供的一些一般性知识,您就可以开始分清正在发生的事情了。

Y函数是“Y组合器”。现在看看 var factorial 使用Y的行。注意,您向它传递了一个具有参数的函数(在本例中, recurse )这在后面的内部函数中也会用到。参数名基本上成为内部函数的名称,允许它执行递归调用(因为它使用 recurse() 在它的定义中。)y-combinator执行将原本匿名的内部函数与传递给y的函数的参数名关联起来的魔力。

为了全面解释Y的魔法,请查看 linked article (顺便说一句,不是我写的。)

对于那些没有深入地遇到函数式编程,不想现在就开始,但有点好奇的程序员:

Y组合器是一个公式,它允许您在函数不能有名称但可以作为参数传递、用作返回值以及在其他函数中定义的情况下实现递归。

它通过将函数作为参数传递给自己来工作,因此它可以调用自己。

它是lambda微积分的一部分,它实际上是数学,但实际上是一种编程语言,对于计算机科学,特别是函数编程来说,它是非常基础的。

Y组合器的日常实用价值是有限的,因为编程语言倾向于让您命名函数。

如果你需要在警察队伍中识别它,看起来是这样的:

Y=_»F.(_»X.F(X X X))(_»X.F(X X X))。

你通常可以发现它,因为重复 (λx.f (x x)) .

这个 λ 符号是希腊字母lambda,它给lambda演算起了名字,有很多 (λx.t) 因为这就是lambda演算的样子。

其他答案提供了非常简洁的答案,没有一个重要的事实:您不需要以这种复杂的方式用任何实际语言实现定点组合器,这样做没有实际意义(除了“看,我知道Y组合器是什么”)。这是一个重要的理论概念,但实践价值不大。

下面是y-combinator和factorial函数的javascript实现(摘自Douglas Crockford的文章,网址: http://javascript.crockford.com/little.html )

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

Y组合器是磁通电容器的另一个名称。

我在《Clojure》和《Scheme》两本书中都为Y-Combinator写了一种“白痴指南”,以帮助自己解决这个问题。他们受到“小阴谋家”的材料影响

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

或Culjule: https://gist.github.com/z5h/5102747

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

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组合器只在按名称调用的语言中工作。如果您想在任何按值语言的正常调用中使用它,那么您将需要相关的Z组合器(Y组合器将发散/无限循环)。

匿名递归

定点组合器是一个高阶函数。 fix 定义上满足等价性

forall f.  fix f  =  f (fix f)

fix f 表示解决方案 x 到定点方程

               x  =  f x

自然数的阶乘可以用

fact 0 = 1
fact n = n * fact (n - 1)

使用 修理 对于一般/递归函数的任意构造证明可以在没有非对称自参照性的情况下得到。

fact n = (fix fact') n

哪里

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

这样

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

这个正式的证据

fact 3  =  6

系统地使用定点组合器等价 重写

fix fact'  ->  fact' (fix fact')

λ演算

这个 非类型化lambda微积分 形式主义包含在上下文无关的语法中

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

哪里 v 变量范围,以及 贝塔 和 η归约 规则

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

贝塔约简替换变量的所有自由出现 X 抽象体中 B 通过表达式(参数) E . ETA减少消除了冗余抽象。它有时被从形式主义中省略。安 不可约的 不适用缩减规则的表达式位于 正常的 或 标准形 .

λ x y. E

是

λ x. λ y. E

(抽象多元性)

E F G

是

(E F) G

(应用程序左关联性)

λ x. x

和

λ y. y

是 α当量 .

抽象和应用是lambda微积分中仅有的两个语言原语,但它们允许 编码 任意复杂的数据和操作。

教会数字是自然数字的编码,类似于皮诺公理化的自然数字。

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

正式的证据

1 + 2  =  3

使用beta缩减的重写规则:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

选择符

在lambda演算中, 连接符 是不包含自由变量的抽象。最简单的是: I 身份组合器

X·X

同构于同一函数

id x = x

这种组合器是 组合计算器 就像滑雪系统。

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

β减少不是 强正火 ;并非所有可约化表达式都在β约化下收敛到正常形式。一个简单的例子是ω的发散应用 ω 组合器

λ x. x x

对自己:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

对最左侧的子表达式(__heads_)的简化进行了优先级排序。 应用序 在替换之前规范化参数, 正常秩序 没有。这两种策略类似于热切的评估,例如C,懒惰的评估,例如Haskell。

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

渴望应用阶贝塔约简下的发散

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

因为在 严格的 语义

forall f.  f _|_  =  _|_

但在慢正态贝塔约简下收敛

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

如果一个表达式有一个正态形式,正态贝塔约简会找到它。

Y

的基本属性 Y 定点组合器

λ f. (λ x. f (x x)) (λ x. f (x x))

是由

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

等价性

Y g  =  g (Y g)

同构于

fix f  =  f (fix f)

非类型化lambda演算可以对一般/递归函数的任意构造证明进行编码。

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(乘法延迟,汇合)

对于Churchian非类型lambda微积分,已经证明存在一个递归可枚举的无穷多的定点组合器,此外 Y .

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

正态贝塔约简使非扩展非类型化lambda演算成为一个图灵完全重写系统。

在haskell中,固定点组合器可以优雅地实现

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

在评估所有子表达式之前,haskell_的懒惰会正常化为有限。

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

• David Turner: Church's Thesis and Functional Programming
• 阿隆佐·邱奇: An Unsolvable Problem of Elementary Number Theory
• Lambda calculus
• Church–Rosser theorem

定点组合器(或定点运算符)是计算其他函数定点的高阶函数。此操作在编程语言理论中是相关的,因为它允许以重写规则的形式实现递归,而无需语言的运行时引擎的显式支持。(SRC维基百科)

此操作员可以简化您的生活:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

然后您就可以避免额外的功能:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

最后,你打电话来 fac(5) .

作为组合器的新手,我发现 Mike Vanier's article (感谢尼古拉斯·曼库索)真的很有帮助。我想写一个总结,除了记录我的理解,如果能对其他人有所帮助,我会非常高兴。

从 蹩脚的 到 不那么蹩脚

以factorial为例,我们使用以下内容 almost-factorial 用于计算数字阶乘的函数 x :

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

在上面的伪代码中, 几乎因式分解 承担职能 f 数 X ( 几乎因式分解 是课程化的,所以它可以被视为承担职能 f 并返回一个1-arity函数)。

什么时候? 几乎因式分解 计算阶乘 X ,它将factorial的计算委托给 x - 1 发挥作用 f 并用 X (在这种情况下,它将(x-1)的结果乘以x)。

可以看出 几乎因式分解 接纳一个 蹩脚的 阶乘函数的版本(只能计算到数字 X—1 )返回一个 不那么蹩脚 阶乘的版本(计算整数 X )如本表所示:

almost-factorial crappy-f = less-crappy-f

如果我们反复通过 不那么蹩脚 factorial to的版本 几乎因式分解 我们最终会得到我们想要的阶乘函数。 f . 其中可以认为:

almost-factorial f = f

固定点

事实是 almost-factorial f = f 方法 f 是 固定点 函数的 几乎因式分解 .

这是一个非常有趣的方法,可以看到上面函数之间的关系,对我来说这是一个非常有趣的时刻。(如果没有,请阅读Mike关于固定点的帖子)

三大功能

概括地说,我们有一个 非递归 功能 fn (就像我们的几乎阶乘一样),我们有 固定点 功能 fr (像我们的F),然后呢? Y 是你付出的时候 Y FN , Y 返回的定点函数 FN .

总之(通过假设简化 FR 只取一个参数; X 退化到 X—1 , x - 2 …在递归中):

• 我们定义了 堆芯计算 作为 FN : def fn fr x = ...accumulate x with result from (fr (- x 1)) 这是 几乎有用 功能-尽管我们不能使用 FN 直接对 X 很快就会有用的。这个非递归的 FN 使用函数 FR 计算其结果
• fn fr = fr , FR 是 FN , FR 是 有用的 功能,我们可以使用 FR 在 X 为了得到我们的结果
• Y fn = fr , Y 返回函数的固定点, Y 转向我们 几乎有用 功能 FN 进入之内 有用的 FR

派生 Y (未包括在内)

我将跳过 Y 去理解 Y . 迈克·维纳的文章有很多细节。

形式 Y

Y 定义为 λ演算 格式:

Y f = λs.(f (s s)) λs.(f (s s))

如果我们替换变量 s 在函数的左边,我们得到

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

因此,事实上, (Y f) 是 f .

为什么 (Y) 工作?

取决于签名 f , (Y) 可以是任何arity的函数,为了简化,我们假设 (Y) 只接受一个参数,就像我们的阶乘函数。

def fn fr x = accumulate x (fr (- x 1))

自从 FN FR=FR 我们继续

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

当最内部的 (fn fr 1) 是基本情况 FN 不使用 FR 在计算中。

看着 Y 再一次:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

所以

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

对我来说,这个装置的神奇部分是:

• FN 和 FR 相互交叉: FR “包装” FN 里面,每次 FR 用于计算 X ,它“产卵”(“提升”?)安 FN 将计算委托给 FN (传递本身 FR 和 X );另一方面, FN 取决于 FR 及用途 FR 计算小问题的结果 x-1 .
• 当时 FR 用于定义 FN (什么时候 FN 使用 FR 在其操作中),真实 FR 尚未定义。
• 它是 FN 它定义了真正的业务逻辑。基于 FN , Y 创造 FR -一个特定形式的助手函数-以便于计算 FN 在一个 递归的 态度。

它帮助我理解 Y 现在这样,希望能有所帮助。

顺便说一句,我还找到了那本书 An Introduction to Functional Programming Through Lambda Calculus 很好,我只是部分通过它,事实上我不能得到我的头周围。 Y 在这本书里我领到了这篇文章。

以下是对 original questions 编译自 the article (完全值得一读)中提到的 answer by Nicholas Mancuso 以及其他答案:

什么是Y组合?

Y组合器是一个“函数”(或高阶函数“对其他函数进行操作的函数”),它接受一个参数,该参数不是递归函数,并返回一个递归函数的版本。

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

组合器只是一个没有自由变量的lambda表达式。
自由变量是一个非约束变量的变量。
绑定变量“变量”,它包含在lambda表达式的主体中,该变量名作为其参数之一。

另一种考虑这一点的方法是,组合器就是这样一个lambda表达式,在这个表达式中,您可以在找到组合器的所有地方用它的定义替换它的名称,并使所有的东西都能工作(如果组合器在lambda体中包含对自身的引用,您将进入一个无限循环)。

Y组合器是一种定点组合器。

函数的固定点是由函数映射到自身的函数域的元素。
这就是说, c 是函数的固定点 f(x) 如果 f(c) = c
这意味着 f(f(...f(c)...)) = fn(c) = c

组合器是如何工作的?

下面的例子假设 强+动态 打字:

惰性(正常顺序)Y组合器:
此定义适用于具有惰性(也包括:延迟、按需调用)评估“评估”策略的语言,该策略将表达式的评估延迟到需要其值为止。

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

这意味着,对于一个给定的函数 f (非递归函数),首先通过计算得到相应的递归函数 λx.f(x x) ,然后将此lambda表达式应用于自身。

严格(应用顺序)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)))

它和懒惰的一样,只是有一个额外的 λ 包装器延迟lambda的体评估。我问过 another question 与这个主题有些关联。

它们有什么用?

偷 借来 answer by Chris Ammerman :y-combinator概括递归,抽象其实现,从而将其与相关函数的实际工作分离。

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

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

AS stated by Mike Vanier : 在许多静态类型语言中定义Y组合器是可能的,但是(至少在我看到的示例中)这种定义通常需要一些不明显的类型黑客,因为Y组合器本身没有直接的静态类型。这超出了本文的范围,所以我不再赘述。

作为 mentioned by Chris Ammerman :大多数程序语言都有静态类型。

所以对这个问题的回答不是真的。

我认为最好的解决方法是选择一种语言,如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组合器解决了什么问题。