问题标签 [y-combinator]

我花了一天时间阅读The Little Schemerlength≤1一书中的第 166 页；有以下代码：

其中lis(apples)和eternityis 如下：

第 166 页（第 4 版）指出：

当我们申请mk-length一次时，我们得到length≤1

进而

我们可以多次这样做吗？

但我不知道如何做到这一点length≤2？

Agda归纳数据类型和模式匹配手册说明：

为了确保归一化，感应事件必须出现在严格的正位置。例如，不允许使用以下数据类型：

因为在构造函数的参数中有一个负面的 Bad 出现。

为什么这个要求对于归纳数据类型是必要的？

我想了解这个结构。有人可以对此代码给出清晰简单的解释吗？

例如，假设我忘记了 Y 的公式。我怎么能记住它，并在我使用它很久之后重现它？

我无法理解 Y-combinator，所以我尝试实现一个在没有本地实现的情况下启用递归的函数。经过一番思考，我最终得出了这个结论：

这比实际的短：

而且，令我惊讶的是，它奏效了。一些例子：

两个片段都按预期输出 10（从 0 到 4 的总和）。

这是什么，为什么它更短，为什么我们更喜欢更长的版本？

我正在尝试实现Lambda-calculus, Combinators and Functional Programming一书中描述的阶乘 lambda 表达式

它的描述方式是：

在哪里

和is-zero, one,multiply和predecessor是为标准教会数字定义的。实际定义在这里。

我将其翻译为以下内容

和

注释掉的版本是Rosetta 代码中的等效 fac 和 Y 函数。

问题一：

我从其他地方的阅读中了解到Y-rosettaβ-减少到Y-mine. 在这种情况下，为什么最好使用那个而不是另一个？

问题2：

即使我使用Y-rosetta. 我尝试时收到 StackOverflowError

尽管

工作正常。

无人看管的递归发生在哪里？

我怀疑这与if表单在 clojure 中的工作方式有关，这并不完全等同于我的is-zero实现。但我自己无法找到错误。

谢谢。

更新：

考虑到@amalloy 的回答，我fac-mine稍作改变以采取懒惰的论点。我对clojure不是很熟悉，所以这可能不是正确的方法。但是，基本上，我is-zero采用匿名零参数函数并评估它返回的任何内容。

我现在收到一条错误消息：

考虑到lazy-next-term总是用nand调用这似乎真的很奇怪f

我正在尝试stack使用定点组合器在 lambda 演算中定义数据结构。我正在尝试定义两个操作，insertion以及removal元素的 sopush和pop，但我能够定义的唯一一个操作，即插入，无法正常工作。删除我无法弄清楚如何定义。

这是我的push操作方法，以及我对 a 的定义stack：

我的堆栈用一个元素初始化以指示底部；我在0这里使用：

但是现在，当我尝试插入另一个元素时，它不起作用，因为我的初始结构已被解构。

如何修复STACK定义或PUSH定义，以及如何定义POP操作？我想我必须应用一个组合器来允许递归，但我不知道该怎么做。

参考：http ://en.wikipedia.org/wiki/Combinatory_logic

任何关于 lambda 演算中数据结构定义的进一步解释或示例将不胜感激。

启发了这篇文章。

我试图用嵌套的 lambda 实现一个斐波那契数列-

是提示r5rs:body: no expression in body in: (r5rs:body)

通过我的检查，每个功能在这里都有一个“身体”，那么我做错了什么？

请注意，我在这里尝试执行的实现是迭代模式，避免重新计算以前的系列..

编辑 ：

另一种也有效的模式 -

我是定点组合器世界的新手，我猜它们习惯于在匿名 lambda 上递归，但我还没有真正使用它们，甚至无法完全理解它们。

我已经在 J​​avascript 中看到了Y 组合器的示例，但无法成功运行它。

这里的问题是，有人可以给出一个直观的答案：

• 什么是定点组合器（不仅在理论上，而且在某些示例的上下文中，以揭示该上下文中的定点究竟是什么）？
• 除了 Y 组合器之外，还有哪些其他类型的定点组合器？

加分项：如果示例不只是使用一种语言，最好也使用Clojure。

更新：

我已经能够在Clojure中找到一个简单的示例，但仍然很难理解 Y-Combinator 本身：

虽然这个例子很简洁，但我发现很难理解函数中发生了什么。提供的任何帮助都会很有用。

我一直在研究禁止 use-before-def 并且没有可变单元格（no set!or setq）的语言如何提供递归。我当然遇到了（著名的？臭名昭著的？）Y 组合器和朋友，例如：

• http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
• http://okmij.org/ftp/Computation/fixed-point-combinators.html
• http://www.angelfire.com/tx4/cus/combinator/birds.html
• http://en.wikipedia.org/wiki/Fixed-point_combinator

当我以这种风格实现“letrec”语义时（也就是说，允许定义一个局部变量，使其可以是一个递归函数，在幕后它永远不会引用它自己的名字），组合器我最终写成这样：

或者，分解出 U 组合子：

将其读作： Y_letrec 是一个函数，它接受一个待递归函数f。 f必须是一个接受的单参数函数s，其中s是f可以调用实现自递归的函数。f预计将定义并返回执行“真实”操作的“内部”函数。该内部函数接受参数a（或者在一般情况下是参数列表，但不能用传统符号表示）。调用 Y_letrec 的结果是调用的结果 f，并且它被假定为一个“内部”函数，准备被调用。

我这样设置的原因是我可以直接使用待递归函数的解析树形式，而无需修改，只需在处理 letrec 时在转换过程中围绕它包裹一个额外的函数层。例如，如果原始代码是：

那么转换后的形式将是：

请注意，两者之间的内部函数体是相同的。

我的问题是：

• 我的 Y_letrec 函数常用吗？
• 它有一个公认的名字吗？

注意：上面的第一个链接引用了与“应用顺序 Y 组合器”类似的函数（在“步骤 5”中），尽管我在找到该命名的权威来源时遇到了麻烦。

2013 年 4 月 28 日更新：

我意识到上面定义的 Y_letrec非常接近但不等同于维基百科中定义的 Z 组合子。根据 Wikipedia，Z 组合器和“按值调用 Y 组合器”是同一个东西，看起来这确实是更常被称为“应用顺序 Y 组合器”的东西。

所以，我上面所说的与通常写的应用顺序 Y 组合子不同，但几乎可以肯定它们是相关的。这是我进行比较的方法：

从...开始：

应用内部 U：

应用外部 U：

重命名以匹配 Wikipedia 对 Z 组合子的定义：

将此与维基百科的 Z 组合器进行比较：

显着的区别在于函数f的应用位置。有关系吗？尽管存在这种差异，这两个功能是否等效？

Knights of the Lambda Calculus 徽标的无穷大写为(Y F) = (F (Y F))

这个lisp代码是一样的吗？它也代表无穷大吗？

(Y (λ (F) (YF)))