定点组合器

Question

我是定点组合器世界的新手,我猜他们已经习惯了匿名的lambdas,但我还没有真正使用它们,甚至无法完全绕过它们.

我在Javascript中看到了Y-combinator的例子,但是还没能成功运行它.

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

• 什么是定点组合器(不仅在理论上,而且在某些示例的上下文中,揭示该上下文中的定点究竟是什么)？
• 除了Y-combinator之外,还有哪些其他类型的定点组合器？

奖励积分:如果示例不仅仅是一种语言,最好也是在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-combinator,你可以先将事实抽象为类似的东西

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

这需要一个参数(myFact),它调用的是"真实的"事实本身.我把这种功能称为"Y-ready",这意味着它已经准备好被送到Y-combinator了.

Y-combinator使用factMaker来构建与"真实"事实相当的东西.

newFact = Y(factMaker)

何必？两个原因.第一个是理论上的:如果我们可以使用Y-combinator"模拟"它,我们真的不需要递归.

第二是更务实.有时我们想用一些额外的代码来包装每个函数调用来进行日志记录或分析或记忆或许多其他事情.如果我们尝试对"真实"事实这样做,那么额外的代码只会被调用到原始的事实调用,而不是所有的递归调用.但是如果我们想为每次通话都做到这一点,包括所有的递归调用,我们可以做类似的事情

loggingFact = LoggingY(factMaker)

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

所有这些都是为什么Y-combinator比Y的特定实现如何工作的详细解释更有动力(因为有许多不同的方法来实现Y).