问题标签 [y-combinator]

注意：这是一种家庭作业，有点不是——最终目标是让一个函数产生一组数字的幂集，作为数字列表提供给函数。我有该函数的递归版本，但我现在需要找到一些方法，用等效的 lambda-only 表达式替换我拥有的解决方案（等）append中的每个显式递归函数。mapm

因此，我从较小的问题开始，并希望将它们全部结合起来编写一个完整的函数。我已经设法使用纯 lambda（Y 组合器）提出了一个非递归阶乘函数，但我现在正试图提出一个很好的函数，它将列表中的每个数字平方 - 尝试在跳跃之前解决较小的问题最多一个乘法递归函数：

上面的代码不会递归，尽管它之前存在 Y 组合器——我显然在将正确的参数传递给其中的函数时遇到了一些问题——有什么想法吗？

我试图解决最大子序列和问题并提出了一个neato解决方案

您调用包装函数msss，然后调用f，这反过来又实际完成了工作。解决方案很好，而且 afaik 工作正常。如果由于某种原因我必须解决生产代码中的最大子序列和问题，那我就是这样做的。

然而，这个包装函数真的让我很烦。我喜欢在 haskell 中的方式，如果你足够坚持，你可以在一行上编写你的整个程序，真正让人们明白程序几乎只是一个大表达式。所以我想我会尝试消除包装函数来应对额外的挑战。

现在我遇到了经典问题：如何进行匿名递归？当你不能给函数命名时，你如何进行递归？值得庆幸的是，计算之父很久以前就通过发现定点组合器解决了这个问题，其中最受欢迎的是Y 组合器。

我已经进行了各种尝试来设置 Y 组合器，但它们无法通过编译器。

只是给

改变从 只是f (y y f)给f (y f)

我已经尝试通过仅在外部定义组合器来采用不同的方法，但这仍然不起作用，并且并没有真正满足我在一个表达式中完成它的挑战。

你能看出我在做什么有什么问题吗？我不知所措。对构造无限类型的抱怨真的让我很生气，因为我认为 Haskell 就是这样的事情。它有无限的数据结构，那么为什么会有无限类型的问题呢？我怀疑这与显示无类型 lambda 演算不一致的悖论有关。不过我不确定。如果有人能澄清一下就好了。

另外，我的印象是递归总是可以用折叠函数来表示。谁能告诉我如何仅使用折叠来做到这一点？尽管如此，代码是单个表达式的要求仍然存在。

我有一个递归函数（在 C# 中），我需要调用大约 8 亿次；这显然通常会在第 900 次调用后导致堆栈溢出。我已经将它踢出多个循环，但递归模式更容易维护，也更清洁。

我正在考虑使用 y-combinator 实现递归函数，正如我正在阅读和看到的那样，这应该可以解决堆栈溢出问题，并修复多个嵌套循环。

有人有使用 y-combinator 的经验吗？我还会被困在堆栈溢出中吗？

以阶乘的简单示例为例。大多数大于 5,000 的数字的阶乘将导致堆栈溢出。如果我在那种情况下正确使用了 y 组合器，它会修复堆栈溢出吗？

实施起来似乎并不简单，所以我想在我花费开发工作/资源实施和学习 y-combinator 之前确认它。

为什么这个函数的类型是(a -> a) -> a？

它不应该是无限/递归类型吗？我打算尝试用文字表达我认为它应该是什么类型，但由于某种原因我无法做到。

我不明白 f (yf) 如何解析为一个值。以下对我来说更有意义：

但这仍然令人困惑。这是怎么回事？

我正在尝试使用 y-combinator 在 scala 中定义 gcd：

但我收到一个错误：

如果我将所有论点都归结起来，那么就没有问题：

我在非咖喱版本中做错了什么？

在尝试了解 Y-Combinator 一个小时后......我终于明白了，但后来我意识到没有它也可以实现同样的事情......虽然我不确定我是否完全理解它的目的。

例如。使用 Y-Combinator 的阶乘

通过引用另一个 lambda 中的函数来实现阶乘

谁能告诉我 Y-Combinator 在 python 中是否有目的？

我有这个任务要做，我需要解析一个错误的书面递归过程，并修复它。例如：这个：

转换成这样：

该过程以引用的形式给出，包含 3 个部分：“let”、let 的 the 和主体。我想解析第二部分（意思是，我想列出一个列表，其中的每个术语都是“let”表达式中的一个单词），但无论我尝试什么，我似乎都无法解决。

我正在使用 drRacket 方案。

感谢和抱歉这么长的信息。

因此，我花了很多时间阅读和重新阅读The Little Schemer中第 9 章的结尾，其中为该length功能开发了应用 Y 组合器。我认为我的困惑归结为一个对比两个版本的长度的声明（在组合器被分解之前）：

第 170 页（第 4 版）指出，A

当我们将它应用于参数时返回一个函数

而乙

不返回函数

从而产生自我应用的无限倒退。我被这件事难住了。如果 B 受到这个问题的困扰，我看不出 A 是如何避免的。

关于 Y 组合器的Wikipedia 文章提供了 Y 组合器的以下 JavaScript 实现：

JavaScript 中 Y 组合子的存在应该意味着每个 JavaScript 函数都有一个固定点（因为对于每个函数g，Y(g)并且g(Y(g))应该相等）。

然而，想出没有固定点的函数并不难Y(g) = g(Y(g))（见这里）。甚至某些泛函也没有固定点（参见此处）。

每个函数都有一个不动点的证明如何与给定的反例相一致？Y(g) = g(Y(g))JavaScript 不是适用于证明的无类型 lambda 演算吗？

这是代码（也在这里）：

当我运行它时：

屏幕截图如下所示：

我使用 DrRacket 作为 repl。代码有什么问题？