math - 自定义类型上的函数的定点组合器？

Question

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

Answer 1

你会在Andrej Bauer的博客上找到这样的计算不动点的函数；例如看似不可能的程序和有限时间内的无限搜索。这是针对固定点实际上处于“有限距离”的情况，以便可以到达。

您所说的一些固定点不是这种类型的，因为它们确实“无限远”。这些是可计算分析中使用的固定点类型。基本上，那里的理论都是关于如何获得对不动点的良好近似。