了解 Y-Combinator 的实现

Question

我想详细了解一下我们是如何从 Y 组合器的 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 演算以及替换过程的工作原理有一定的了解。然而，我很难理解我们是如何从正式表达到实现的。

此外，我很想知道如何区分类型和数量的参数我的函数及其 return 类型 任何 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))

由于是递归的，我们需要添加一个return类型：

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

Answer 2

请注意，您编写的不是 Y 组合器的实现。 “Y 组合器”是 λ 演算中的特定 "fixed-point combinator"。术语 g 的 "fixed-point" 只是一个点 x 这样，

g(x) = x

A "fixed-point combinator" F 是可用于 "produce" 固定点的术语。也就是说，

g(F(g)) = F(g)

项 Y = λf.(λx.f (x x)) (λx.f (x x)) 是众多服从该等式的项之一，即 g(Y(g)) = Y(g) 在某种意义上可以将一项简化为另一项。这个属性就是指这样的项，包括Y在微积分中都可以用到"encode recursion"。

关于打字，请注意 Y 组合子不能在简单打字的 λ 演算中打字。甚至在系统 F 的多态演算中也没有。如果你尝试输入它，你会得到 "infinite depth" 的类型。要键入它，您需要在类型级别进行递归。所以如果你想扩展例如只需将 λ 演算键入您提供 Y 作为原语的小型函数式编程语言。

虽然你没有使用 λ 演算，但你的语言已经带有递归。所以你写的是 Scala 中定点 "combinator" 的直接定义。直截了当，因为作为不动点（几乎）立即从定义中得出。

Y(f)(x) = f(Y(f))(x)

对所有 x 都是正确的（并且它是一个纯函数）因此，

Y(f) = f(Y(f))

这是不动点的方程。关于 Y 类型的推断，考虑等式 Y(f)(x) = f(Y(f))(x) 并让

f : A => B
Y : C => D

因为 Y : C => D 将 f : A => B 作为输入，那么

C = A => B

因为 Y f : D 是 f : A => B 的输入，所以

D = A

并且由于输出 Y f : D 与 f(Y(f)) : B 的输出相同，因此

D = B

到目前为止，

Y : (A => A) => A

由于Y(f)应用于x，Y(f)是一个函数，所以

A = A1 => B1

对于某些类型 A1 和 B1 因此，

Y : ((A1 => B1) => (A1 => B1)) => A1 => B1

了解 Y-Combinator 的实现

Understanding the implementation of Y-Combinator

scala

recursion

functional-programming

lambda-calculus

y-combinator