问题标签 [y-combinator]

Y 组合子（来自维基百科文章）定义为：

Y = \f.(\x.f(x x)) (\x.f(x x))

所以当我们在 g 上调用 Y 时：

重复导致：

因为这个展开是在一元函数之上的，所以我不知道这是左折叠还是右折叠。

我对左折叠的理解是它类似于这个（使用二元函数 f）：

而二进制函数 f 的右折叠如下所示：

但是，我想任何一元函数看起来都与左折叠或右折叠扩展相同：

这个对吗？如果不是，Y 组合器是展开成左折叠还是右折叠？

我正在观看 Jim Weirich 的演讲：https ://www.youtube.com/watch?v=FITJMJjASUs关于在 Ruby 中实现 Y-Combinator，并在 Swift 中跟进。

我最终得到了这个函数，它可以作为高达 5 的数字的阶乘：

接下来发生的事情是他删除error了 ，他的代码仍然有效：

在 Swift 中，这是一个编译器失败，因为generator它期望(Int) -> Int作为输入，但获得了一个generator类型。

相反，我们可以如下实现 Y 组合器：

但是上面的问题是该Y函数在该行中引用了自己：

let recursiveWorker = Y(generator)

在我看来，这违背了这个练习的全部目的。

我的问题是：是否可以在 Swift 中实现与演讲中相同的代码？也就是说，创建一个闭包 Y-combinator？还是因为 Swift 的静态类型而这不可能？

我们可以定义一个递归函数，factorial例如，YCombinator如下

我已经了解了 Y 组合器是什么，并且知道它是如何以数学方式定义的。

但我发现很难实施。特别是，我对 的定义YCombinator似乎更接近数学定义，但未能定义factorial。

问题

1. 为什么会这样？我错过了什么？
2. 为什么我们需要设置lexical-binding为t？
3. (e)lisp 翻译器是否有 lambda 表达式？

三天以来，我一直在阅读有关组合器的信息，终于开始用代码编写它们（更像是从不同地方复制东西并理解事物）。

这是我正在尝试运行的一些代码：

如果我将 lambda 的返回类型明确声明为-> int64_t，则一切正常。但是，当我删除它时，编译器会抱怨。错误：

为什么编译器无法确定返回类型并推断出 auto？我首先想到，也许我需要更改... ? 1 : n * self(n - 1)为，... ? int64_t(1) : n * self(n - 1)以便两个返回值的类型最终都为int64_t，并且不会留下任何可能的歧义。不过，情况似乎并非如此。我错过了什么？

此外，在y_combinator类中，声明lambda为类型的对象Lambda&&似乎会导致问题。为什么会这样？这只发生在我将operator ()重载中的强制转换写为(decltype(*this)&)而不是std::ref(*this). 他们在做不同的事情吗？

我正在尝试使用类似 y-combinator 的 lambda 包装（尽管我知道它们实际上并不是严格意义上的 y-combinator），但我遇到了一个非常奇怪的问题。我的代码完全按照我在 Debug 配置中的预期运行（关闭了优化），但在 Release 中跳过了大（而且很重要！）位（设置为Optimizations (Favor Speed) (/Ox)）。

请注意，lambda 函数的内部基本上是不相关的，它们只是为了确保它可以正确递归等。

应该发生的是，第一次评估d工作正常，设置d.m_selfDestructTrigger并导致自身被删除。然后第二次评估d应该崩溃，因为d不再真正存在。这正是调试配置中发生的事情。（注意：正如@largest_prime_is_463035818 在下面指出的那样，它不应该像遇到未定义的行为那样崩溃。）

但据我所知，在 Release 配置中，所有代码都evaluate被完全跳过，执行直接跳转到 lambda。显然，优化代码中的断点有点可疑，但这似乎就是正在发生的事情。我试过重建项目，但没有骰子；VS 似乎对此非常坚定。

我疯了吗？有什么我错过的吗？或者这是 VS（甚至是编译器）中的实际错误？在确定这是代码问题还是工具问题方面的任何帮助将不胜感激。

注意：我在 VS2019 16.8.3 上，使用/std:c++ latest功能集。

我正在尝试构建一个干净整洁的具有递归能力的 lambda 自作用域的实现（它基本上是一个 Y 组合器，尽管我认为技术上并不完全）。这是一个带我去的旅程，除其他外，这个线程和这个线程和这个线程。

我已经尽可能清楚地总结了我的一个问题：如何传递以 lambda 作为其模板参数的模板仿函数？

上面的代码不起作用，Visual Studio 声称f（在b.evaluate(f)调用中）与参数类型不匹配。

我的假设是这auto & self还不够聪明，无法完成这项工作。我该如何解决这个问题？当它们基本上无法定义时，我如何存储和传递这些东西？这就是为什么我见过的许多 Y-combinator 实现都有奇怪的双重包装的原因吗？

任何帮助或解释将不胜感激。

在这个 Y-combinator 的解释中（https://mvanier.livejournal.com/2897.html），

它说阶乘 A 的定义将进入标准方案中的无限循环，但是实现它会给出一个错误，说阶乘 A 没有定义。

我认为这是预期的，因为当我们定义（如果不是使用 lambda）时，我们正在评估最终将计算参数的定义，其中一个是尚未定义的相同函数。

这是正确的，那么我们如何解释上面的文章呢？谢谢

给定一个列表，例如(f: f FALSE (g: g FALSE (h: h TRUE FALSE)))，编写一个删除所有前导FALSEs 并仅返回以 开头的尾部的运算符TRUE。对于此示例，运算符应仅返回(h: h TRUE FALSE).

这是一个练习，实际上是一个关卡，在这个名为“功能性”的游戏中，我已经迷上了它。在之前的级别中，我们需要将 \Omega 推广到 y 组合器中，所以我想这个级别需要 y 组合器来处理FALSE任意长度的前缀。

我可以FALSE使用(b: c: IF b (f: f b c) c). 想象那个运算符，因为f我猜答案应该看起来像(b: c: IF b (f: f b c) (Y c)). 游戏拒绝那个抱怨“没有减少（变得太大）”的答案。

我显然对 y-combinator 感到困惑。有人可以告诉我如何正确使用它吗？

另外，游戏使用的这种疯狂语法是什么？我没有看到它在其他任何地方使用过。

根据要求，此处提供了 Steam 上功能性页面的链接。我最近还在这里发现了 github 上的项目页面链接。

我正在寻找的是以其他形式重写 Y 组合器......

原始符号： Y := λf.(λx.f(xx))(λx.f(xx))

首先，通过指出右侧表达式是一个应用程序来减少混淆的符号：

Y := λfx.f(xx)[x:=λx.f(xx)] 这个对吗？

那么，这些是 Y 的所有功能等价物吗：

包括M := λf.ff（知更鸟）

1. Y := λf.λx.M(f(xx)) [x:=λx.f(xx)]

2. Y := λfx.M(fxx) [x:=λx.f(xx)]

3. Y := λfx.f(fMx) [x:=λx.f(xx)]

4. Y := λfx.M(fMx) [x:=λx.f(xx)]

上述任何（据说）beta 减少到： Yz -> z(Y z)

问题是这些有效吗？

作为 CompSci 学位的一部分，我刚开始学习 Lambda 微积分。在课程材料中（这不是评分作业，不用担心！）出现了以下 beta 减少：

. → .() → .(()) → .((()))

我有点困惑，因为我认为我们不能在 beta 减少步骤中添加一些东西。任何人都可以向我解释一下，或者给我一些提示，说明为什么会这样？任何帮助表示赞赏。谢谢！