问题标签 [fixpoint-combinators]

以这个示例代码为例（暂时忽略它非常低效）

这是我在 F# 中经常遇到的一种常见模式，我需要一个内部函数，它在某个值上递归自身 - 我只需要这个函数一次，有没有可能从它自身内部调用一个 lambda（一些魔术关键字或其他东西）？我希望代码看起来像这样：

但是正如您可能期望的那样，没有办法在其内部引用匿名函数，这是我放置##RECURSE##的地方所需要的

我正在尝试了解组合器，但我无法理解（Y 覆盖自我应用程序）中给出的示例。我想我开始掌握这个概念，但我离理解还很远。

我想将以下代码翻译成 Python：

我通过写作尝试了“字面”翻译：

但这不起作用（我认为这与函数在 lambda 内部评估的顺序有关）。

所以我尝试将函数组合用作：

但是仍然没有用，当调用我的最后一段代码时，我得到了一个 lambda：

那么，是否可以用 Python 编写给定示例的“字面”翻译？我怎么能做到？

大多数使用定点组合器的示例都涉及将整数转换为整数的函数（例如阶乘）。在许多情况下，实数上的函数的不动点最终会成为任意有理数或可能是无理数（一个著名的例子是逻辑图http://en.wikipedia.org/wiki/Logistic_map）。在这些情况下，固定点可能不会用原始类型表示（请注意，尽管 Clojure 确实支持比率）。我有兴趣了解可以在这些“奇异”类型上计算函数的定点的定点组合器（及其实现！）。由于诸如无理数之类的事物将十进制表示为无限序列，因此似乎必须对这种计算进行惰性评估。这些（假定的）惰性评估中的任何一个是否会产生对真实不动点的良好近似？我的目标语言是 Python 和 Clojure，但我当然不介意看到任何 OCaml 或 Haskell 实现）。

我对某事感到困惑。我想生成一个示例（在 Clojure 中），演示如何使用定点组合器来评估序列的定点，该序列在无限数量的应用程序后数学上收敛，但实际上会在有限数量的步骤后收敛浮点数的有限精度。我显然在这里遗漏了一些东西。

然后我可以得到

我不明白这个堆栈溢出。更一般地说，与我之前的帖子相关，我想知道是否有人可以提出一个“正确”版本的定点组合器，它可以用来以这种方式逼近序列的定点。

我正在使用 F# 创建 lambda 演算。我目前正试图弄清楚如何实现定点运算符（也称为 Y 组合器）。

我认为其他一切都井然有序。表达式由以下可区分联合表示：

我的eval功能似乎有效。以下示例都产生了预期的结果。
示例 1：
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
示例 2：
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
示例 3：
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

但正如我所提到的，我很难在我的 lambda 演算中实现定点运算符。这里定义为：
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

有没有人有什么建议？我查看了有关 Y 组合器的其他问题，但找不到任何我能够成功采用的东西。

感谢所有帮助。

编辑：修正了代码中的错字......以前我有Mult而不是Minus在受歧视的工会中。有趣的是我才注意到这一点！

我对文档有点困惑fix（尽管我想我现在明白它应该做什么），所以我查看了源代码。这让我更加困惑：

这究竟是如何返回一个固定点的？

我决定在命令行尝试一下：

它挂在那里。现在公平地说，这是在我的旧 macbook 上，有点慢。然而，这个函数在计算上不能太昂贵，因为任何传入 id 的东西都会返回相同的东西（更不用说它不会占用 CPU 时间）。我究竟做错了什么？

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

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

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

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

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

我正在寻找一个库，该库将在多个可变参数运算符下计算一组的定点/闭包。例如，

因为整数应该计算所有的 N（自然数，1..）。我试着写它，但有些东西是缺乏的。这不是很有效，而且我感觉我对多参数函数的处理不是最优雅的。此外，是否可以使用内置fix函数而不是手动递归来编写？

例子，

设置版本

虽然我想我只需要弄清楚如何减少计算以使其实际上更快，但这并没有提高性能。

设置懒惰的版本

我曾经RMonad把它清理一下，并按照丹尼尔的建议让它变得懒惰。遗憾的是，我认为大部分时间都花在了实际的乘法例程中，所以我没有看到这种变化对性能有任何好处。懒惰虽然很酷。

例子

我不得不失去一元运算，但这不是交易杀手。

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

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

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