functional-programming - 定点组合器

Question

我对fixed-point combinators并不陌生，我猜想它们是用来递归匿名lambda的，但是我还没有真正使用它们，甚至无法完全将它们包裹住。

我已经在Javascript中看到了Y-combinator的示例，但未能成功运行它。

这里的问题是，有人可以给出一个直观的答案:

什么是定点组合器(不仅在理论上，而且在某些示例的上下文中，以揭示该上下文中的确切点是什么)？

除了Y组合器以外，还有哪些其他定点组合器？

奖励积分:如果该示例不仅使用一种语言，还最好使用 和Clojure 。

更新:

我已经能够在 Clojure中找到一个简单的示例，但是仍然很难理解Y-Combinator本身:

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

尽管示例很简洁，但是我发现很难理解函数中正在发生的事情。提供的任何帮助将是有用的。

Answer 1

假设您要编写阶乘函数。通常，您可以将其写为

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

但这使用了显式递归。如果您想使用Y组合器，则可以首先将事实抽象为

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组合器“模拟”它，则实际上并不需要递归。

第二个更务实。有时，我们想给每个函数调用加上一些额外的代码，以进行日志记录，性能分析或备忘录或其他很多操作。如果我们尝试对“真实”事实执行此操作，则只会为原始的事实调用(而不是所有的递归调用)调用额外的代码。但是，如果我们想为每个调用(包括所有递归调用)执行此操作，则可以执行以下操作

loggingFact = LoggingY(factMaker)

其中LoggingY是Y组合器的修改版本，它引入了日志记录。请注意，我们根本不需要更改factMaker!

与对Y的特定实现方式的详细解释(因为实现Y的方式不同)相比，所有这些都是使Y组合器重要的动机。