Y-Combinator实用示例

Question

最近我读了一些关于函数式编程的文章，我正在尝试Y-Combinator。我知道您可以使用Y-Combinator在不直接支持递归的语言中有效地实现递归。然而，我可能使用的每一种语言都已经支持递归，所以我不确定使用Y-Combinator来实现递归有多大用处。

有没有我遗漏的Y-Combinator用法更好的实际例子？有人在实际的生产代码中使用过吗？或者使用Y-Combinator真的只是一个令人费解的学术练习(尽管是一个相当酷的练习)。

Answer 1

我不会同意其他答案：定点(Y)组合器确实有实际应用程序，但需要非常有想象力的头脑才能找到它们。就像Bruce McAdam一样。这是他的论文That About Wraps it Up的摘要

用于计算固定点的Y组合器可以用标准ML表示。它经常被用作高阶函数的强大功能的示例，但通常不被视为有用的编程结构。在这里，我们将研究基于Y组合器和包装器的编程技术如何为程序员提供对函数内部工作的控制级别，否则如果不重写和重新编译代码，这是不可能的。作为实验，使用该技术实现了类型推断算法W，以便在对算法的干扰最小的情况下产生错误消息。这个示例程序的代码说明了这些概念的真正用处以及它们可以很容易地应用。还讨论了许多其他实现技术和可能的应用程序，包括使用高阶函数来模拟异常和延续的使用。

这是一篇很棒的论文；任何对函数式编程感兴趣的人都可能会喜欢阅读它。

Answer 2

你可以看看这篇关于在C#：Recursive Lambda Expressions中实现Y组合子的漂亮文章，它可能会帮助你更好地理解这个想法。

你可能想看看维基百科上的一些不错的文章：Fixed point combinator和Fixed point theorems

正如Nathan所说，许多函数式技术都与Y组合器相关，并且非常有用，所以请坚持下去！Y确实很有用，因为它可以让你更好地理解你的代码，但我不认为这对描述它是如何有帮助的特别有帮助。

Answer 3

如果我错了，其他人可以纠正我，但我很确定Y组合器是严格意义上的。想想看:要实现它，你的语言需要支持高阶函数，而不是递归。我只知道一种语言: lambda演算。

因此，在我们的机器从图灵机切换到运行lambda演算之前，Y组合器将是严格意义上的。

注意:与Y组合器相关的其他函数技术也很有用，因此请继续使用它。了解Y组合器将帮助您理解延续、延迟计算等。