scala - 理解Y-Combinator的实现

Question

我想详细了解我们是如何从 Y-combinator 的 lambda 演算表达式中获得的:

Y = λf.(λx.f (x x)) (λx.f (x x))

到以下实现(在 Scala 中):

def Y[A, B](f: (A => B) => A => B): A => B = (x: A) => f(Y(f))(x)

我对函数式编程很陌生，但我对 lambda 演算以及替换过程的工作原理有很好的理解。然而，我很难理解我们是如何从正式表达到实现的。

此外，我很想知道如何告诉 类型 和 号码 的 参数 我的函数及其 返回类型 不管 lambda ?

Answer 1

首先，Scala 代码的编写方式很长:

def Y[A, B](f: (A => B) => A => B): A => B = f(Y(f))

在这里，f部分应用。 (看起来代码作者选择使用 lambda 来使这更明确。)

现在，我们如何得出这段代码？ Wikipedia notes那个Y f = f (Y f) .将其扩展为类似 Scala 的内容，我们有 def Y(f) = f(Y(f)) .这不能用作 lambda 演算中的定义，它不允许直接递归，但它在 Scala 中有效。为了使其成为有效的 Scala，我们需要添加类型。向 f 添加类型结果是:

def Y(f: (A => B) => A => B) = f(Y(f))

自 A和 B是免费的，我们需要让它们成为类型参数:

def Y[A, B](f: (A => B) => A => B) = f(Y(f))

由于它是递归的，我们需要添加一个返回类型:

def Y[A, B](f: (A => B) => A => B): A => B = f(Y(f))