问题标签 [y-combinator]

为了了解定点组合器的用途和用途，我编写了自己的。但是，我没有使用严格的匿名函数来编写它，例如Wikipedia 的示例，而是使用了定义：

我已经用阶乘和斐波那契的函数对此进行了测试，它似乎有效。这是否符合定点组合器的正式定义？

最近我花了一些时间来研究 Y 组合器，我发现它通常定义（或多或少）如下（这是在 C# 中，但选择的语言并不重要）：

虽然这是完美的功能（双关语），但我的定义似乎要简单得多：

后一个定义不那么普遍（我还没有在网上找到）有什么原因吗？它可能与根据自身定义 Y 有关吗？

是否有用于创建相互递归函数元组的定点组合器？即我正在寻找类似 Y-Combinator 的东西，但它需要多个“递归”* 函数，并且会返回一个函数元组？

*：当然不是真正的递归，因为它们被编写为以通常的 Y-Combinator 方式将自己（和兄弟姐妹）作为参数。

几天前，我在“C# 中的匿名递归”上浏览了这个网站。这篇文章的主旨是以下代码在 C# 中不起作用：

然后，本文详细介绍了如何使用currying和Y-combinator回到 C# 中的“匿名递归”。这很有趣，但恐怕对我的日常编码来说有点复杂。至少在这个时候...

我喜欢自己看东西，所以我打开了 Mono CSharp REPL并输入了那行。没有错误。于是，我进入了fib(8);。令我大吃一惊的是，它奏效了！REPL 回复了21!

我想这可能是 REPL 的一些神奇之处，所以我启动了“vi”，输入以下程序并编译它。

它也完美地构建和运行！

我在 Mac 上运行 Mono 2.10。我现在无法访问 Windows 机器，因此无法在 Windows 上的 .NET 上进行测试。

这是否也已在 .NET 上得到修复，或者这是 Mono 的静默功能？这篇文章是几年前的。

如果它只是 Mono，我等不及下一次工作面试，他们要求我用我选择的语言（Mono C#）编写一个 Fibinocci 函数，我必须提供警告，即 .NET 将无法工作。好吧，其实我可以等，因为我热爱我的工作。不过，有趣的是...

更新：

Mono 并没有真正进行“匿名”递归，因为它fib用作命名委托。我的错。Mono C# 编译器假定分配前的null值fib是一个错误，如下所述。我说“编译器”是因为 .NET CLR 可以很好地运行生成的程序集，即使 .NET C# 编译器不会编译代码。

对于所有纳粹采访：

可以替换为迭代版本：

您可能希望这样做，因为递归版本在 C# 等语言中效率低下。有些人可能会建议使用记忆，但由于这仍然比迭代方法慢，他们可能只是个傻瓜。:-)

不过，在这一点上，这更像是函数式编程的广告（因为递归版本要好得多）。它确实与我最初的问题没有任何关系，但一些答案认为这很重要。

所以我在玩 y-combinator 和匿名函数，我遇到了这个奇怪的错误：

（产生错误的源代码，以及我最终开始工作的版本）

如果我稍微修改类型以避免 Rank N polymorphism (use forall b. Int -> b -> [b] -> [b])，错误是相似的：

有人可以向我解释为什么 forall b. b -> [b] -> [b]没有论据吗？

我有一个根据迭代计算固定点的函数：

请注意，我们可以从中抽象为：

这个函数可以用fix来写吗？似乎应该从这个方案转变为有修复的东西，但我没有看到。

我正在尝试更好地学习 Y 组合器（我在 Scheme 中有点理解它）并在 D 2.0 中实现它，但我失败得很惨：

这不起作用，原因很明显，我无法传递fact给fact（它的类型是什么？）。而且，我仍然需要fact's name 来传递给它自己，所以它无论如何都行不通，对吧？

但是......我该如何在 D 中实现 Y 组合器？

当我偶然发现 Wikipedia 说：“Y 组合子可以在 SKI 演算中表示为：Y = S (K (SII)) ( S（S（KS）K）（K（SII）））”，所以我不得不尝试：

我究竟做错了什么？我没有正确翻译那个表达吗？我的处理方式有问题吗？它甚至有意义吗？大部分关于此类内容的阅读内容只会让我的大脑想要爆炸，所以这个练习的重点对我来说主要是看看我是否理解了这个符号（从而能够将它翻译成 JavaScript）。

哦，顺便说一句：让我再次阅读和摆弄的是prototype.js作为Prototype.K实现的实际上是I组合子。有没有人注意到？

我的大脑似乎处于自虐模式，所以在淹没在这个、这个和这个中之后，它想在 C# 中搞一些 DIY。

我想出了以下内容，我认为它不是Y 组合器，但它似乎确实设法使非递归函数递归，而不涉及自身：

因此，鉴于这些：

我们可以生成这些：

K组合器是和K := (λxy.x)定点组合器是Y := λf.(λx.f x x) (λx.f x x)。我试图计算YK：

所以因为YK是 的不动点K：

对于任何 e。但KIe应该等于I！