固定点组合子

Question

我对 不动点组合器 的世界是新手，我猜它们用于对匿名 lambda 进行递归，但我还没有真正使用过它们，甚至还没有完全理解它们。

我已经在Javascript中看到了一个Y组合子的例子，但我尝试运行时无法成功。

问题是，有没有人能够直观地回答以下问题：

• 什么是不动点组合器（不仅从理论上讲，而是从一些例子的背景下，揭示那种情况下真正的不动点是什么）？
• 除了 Y 组合子之外，还有哪些其他种类的不动点组合器？

加分题：如果例子不只在一种语言中，请优先考虑Clojure。

更新：

我已经在 Clojure 中找到了一个简单的例子，但仍然很难理解Y组合子本身：

(defn Y [r]
  ((fn [f] (f f))
   (fn [f]
     (r (fn [x] ((f f) x))))))

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

- Gaurav Agarwal

---

请参见https://dev59.com/vmUp5IYBdhLWcg3wGEgR#15523799。 - Petr

Answer 1

假设您想编写阶乘函数。通常，您会编写类似以下的内容

function fact(n) = if n=0 then 1 else n * fact(n-1)

但是这种方法使用显式递归。如果您想使用Y组合子，您可以先将fact抽象为以下形式：

function factMaker(myFact) = lamba n. if n=0 then 1 else n * myFact(n-1)

这个函数接受一个参数（myFact），它会调用自己原本被称为“真实”事实的部分。我把这种函数风格称为“Y-ready”，意思是它已经准备好被输入到Y组合器中。

Y组合器使用factMaker构建了与“真实”事实等效的东西。

newFact = Y(factMaker)

为什么要这样做？有两个原因。第一个是理论上的：如果我们可以使用Y组合子来“模拟”递归，那么我们实际上就不需要递归。

第二个原因更实用。有时候我们想要用一些额外的代码来包装每个函数调用，以执行日志记录、性能分析、记忆化或其他一系列操作。如果我们尝试将这些代码应用于“真正”的事实，那么这些额外的代码只会被调用一次，即原始的fact调用，而不是所有的递归调用。但是如果我们想要在每个调用（包括所有递归调用）中执行这些操作，我们可以这样做：

loggingFact = LoggingY(factMaker)

LoggingY 是一个引入日志的修改版 Y 组合子。请注意，我们完全不需要改变 factMaker！

所有这些都更加说明了 Y 组合子的重要性，而不是从特定实现的工作方式进行详细解释（因为有许多不同的实现方式）。

- Chris Okasaki

---

感谢您提供实用的示例，非常有帮助。 :) - Gaurav Agarwal

哇塞..我才意识到..回答我的问题的是Chris Okasaki--《纯函数数据结构》的作者..非常感谢你抽出时间来帮忙解答.. :) - Gaurav Agarwal

Answer 2

为了回答你关于除Y以外的定点组合子的第二个问题。存在可数无限数量的标准定点组合子，也就是满足方程式的组合子fix。

fix f = f (fix f)

还有无限个非标准的不动点组合子，它们满足以下方程式

fix f = f (f (fix f))

等等。标准的不动点组合子是可递归枚举的，但非标准的则不是。请参阅以下网页，其中包含示例、参考资料和讨论。 http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes

- Oleg