问题标签 [y-combinator]

我尝试使用 y-combinator（在 Lua 和 Clojure 中），因为我认为这将允许我在使用递归时超出默认堆栈实现的大小。看来我弄错了。是的，它有效，但是在这两个系统中，堆栈的崩溃与使用普通的旧递归完全相同。Clojure 中的低约 3600 和我的 Android Lua 实现中的高约 333000。它也比常规递归慢一点。

那么使用 y-combinator 有什么好处，还是只是为了证明一个观点而进行的智力练习？我错过了什么吗？

===

PS。抱歉，我应该更清楚地说明我知道我可以使用 TCO 来超过堆栈。我的问题与此无关。我对此很感兴趣 a) 从学术/知识的角度来看 b) 是否可以对那些不能递归编写的函数做任何事情。

我想详细了解一下我们是如何从 Y-combinator 的 lambda 演算表达式中得到的：

到以下实现（在 Scala 中）：

我对函数式编程很陌生，但我对 lambda 演算以及替换过程的工作原理有相当的了解。然而，我很难理解我们是如何从形式表达到实现的。

此外，我很想知道如何告诉我的函数的类型和参数数量以及它的任何lambda的返回类型？

在阅读这篇关于 Y-combinator 的文章（我强烈推荐）时，我偶然发现了这种转换：

有人可以解释一下我们是如何获得第二个版本的 Y 的吗？我们遵循了哪些步骤来实现目标？

这是 Haskell 中定点组合器的通常定义：

在https://wiki.haskell.org/Prime_numbers上，他们定义了一个不同的定点组合器：

_Y是一个非共享定点组合器，在这里安排一个递归的“伸缩”多级素数生产（生产者塔）。

这到底是什么意思？在这种情况下，什么是“共享”与“非共享”？与有何_Y不同？fix

我写了一个像这样的 Y 组合器：

它有效，但是当我尝试定义阶乘时

它会编译，但是当我像f(3)clang一样调用它时，会卡在推断返回类型上。使用显式返回类型，一切正常。这是模板扣除的限制吗？有解决办法吗？

我正在学习 C++。作为对我自己的练习，我正在尝试使用 Y 组合器从非递归版本中定义斐波那契函数。

在 F#（或 C#）中，我会这样做：

在 C++ 中，我被困在如何定义 Y

以便以下几行起作用

我尝试了以下函数声明（特定于 int 函数，因为我还没有研究过模板）：

但我坚持编写函数定义。

有什么建议么？

有谁知道如何在 Scheme 中实现 Y 组合器，特别是使用惰性求值和附加参数？据我了解，Scheme (promise?) (delay) 和 (force) 提供惰性评估支持。

我的理解是带有应用程序的 Y-combinator 如下，但是由于应用程序的顺序评估，默认情况下在 Scheme 中不起作用。

这是一个建议的解决方案（Z-combinator），但是它使用另一个带有参数的 lambda 函数作为解决方案：

基于解决方案的更新

Y-组合器如下：

感谢您的指导！

如果expression计算为一个参数的函数，我会认为 lambda x: ( expression )(x) 与expression相同- 但实际上并非如此。考虑 Y 组合子的以下两个定义：

Y2 实际上按预期工作，但调用 Y1 会引发堆栈溢出。为什么会有这种行为差异？

我正在阅读一本关于 λ 演算的书“通过 Lambda 演算进行函数式编程”（Greg Michaelson）。在书中，作者介绍了定义函数的简写符号。例如

并继续说我们应该坚持在使用这种速记时“所有定义的名称都应该在计算表达式之前被它们的定义替换”

后来，在介绍递归时，他以加法函数的定义为例，例如：

并且可以说，如果我们没有上面提到的限制，我们将能够通过缓慢扩展来评估这个函数。然而，由于我们有在计算表达式之前替换所有定义的名称的限制，我们不能这样做，因为我们继续无限地替换add，因此需要以更详细的方式考虑递归。

因此，我的问题如下：对我们自己施加这种限制的理论或实践原因是什么？（必须在评估函数之前替换所有定义的名称）？有吗？

我对 Python 完全陌生，我被赋予了使用 Y 组合器重写两个 Python 函数的任务。为此，我必须先将它们转换为 lambda，这就是问题所在 - 它们都有多个语句，我在使它们与 lambda 兼容时遇到了麻烦。我一直在阅读有关使用元组或列表的信息，但这似乎不适用于我的情况。

例如，我尝试将最后一个函数编写为以下 lambda：

但是列表中的赋值存在语法错误。

当涉及到这两个功能时，您能指出我正确的方向吗？