使用定点组合器的大多数示例都涉及将整数转换为整数的函数（例如阶乘）。在许多情况下，函数在实数上的不动点最终将成为任意有理数或无理数（一个著名的例子是逻辑映射 http://en.wikipedia.org/wiki/Logistic_map）。在这些情况下，固定点可能不会用原始类型来表示（请注意，Clojure 确实支持比率）。我有兴趣了解定点组合器（及其实现！），它们可以计算这些“奇异”类型的函数的定点。由于无理数之类的东西具有无限序列的十进制表示形式，因此似乎必须延迟计算此计算。这些（假定的）惰性求值是否能很好地近似真实的不动点？我的目标语言是 Python 和 Clojure，但我当然不介意看到任何 OCaml 或 Haskell 实现）。
Most examples of the use of fixed point combinators involve functions that take integers to integers (e.g. factorial). In many cases the fixed point of a function over the real numbers will end up being an arbitrary rational or perhaps irrational number (a famous example is the logistic map http://en.wikipedia.org/wiki/Logistic_map). In these cases the fixed point may not be expressed in terms of primitive types (note though that Clojure does have support for ratios). I am interested in finding out about fixed point combinators (and their implementation!) that can compute fixed points of functions over these "exotic" types. Inasmuch as things like irrational numbers have decimal representation as infinite sequences, it seems like this computation must be evaluated lazily. Do any of these (putative) lazy evaluations yield good approximations to the true fixed points? My target languages are Python and Clojure, but I certainly wouldn't mind seeing any OCaml or Haskell implementations).
发布评论
评论（1）
你会在 Andrej Bauer 的博客上找到这样的计算不动点的函数；例如看似不可能的程序和有限时间内无限搜索< /a>.这是针对固定点实际上处于“有限距离”的情况，因此可以到达该固定点。
你所说的一些固定点不是这种类型的，因为它们确实是“无限远”。这些是可计算分析中使用的固定点类型。基本上，该理论都是关于如何获得固定点的良好近似值。
You will find such function that compute fixed points on Andrej Bauer's blog; for example seemingly impossible programs and infinite search in finite time. That's for the case where the fixed point is actually at a 'finite distance', so that it will be reached.
Some of the fixed points you are talking about are not of this sort, as they really are 'infinitely far away'. These are the types of fixed points which are used in Computable Analysis. Basically the theory there is all about how to obtain good approximations to the fixed point.