代码之家 › 专栏 › 技术社区 › ecdhe

了解Y组合器的实现

y-combinator lambda-calculus functional-programming recursion scala

ecdhe · 技术社区 · 6 年前

我想详细了解一下我们是如何从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 ?

2 回复 | 直到 6 年前

Jorge Adriano Branco Aires 6 年前

注意,您所写的不是 Y 组合器。“ Y “组合器”是微积分中一种特殊的“定点组合器”。术语的“定点” g 只是一个点 x 这样,

g(x) = x

“定点组合器” F 是一个可以用来“产生”固定点的术语。也就是说,

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

术语 Y = Î»f.(Î»x.f (x x)) (Î»x.f (x x)) 是许多遵守这个方程的人中的一个,也就是说,它是这样的 g(Y(g)) = Y(g) 在这个意义上,一个术语可以简化为另一个术语。本财产系指此类条款,包括 Y 可用于微积分中的“编码递归”。

关于打字注意 Y 组合器不能在简单类型的“微积分”中键入。即使在F系统的多态演算中也不行。如果你尝试输入它,你会得到一种“无限深度”的类型。要键入它,需要在类型级别进行递归。所以,如果你想把简单的输入微积分扩展到你提供的一种小的函数式编程语言 Y 作为原语。

但是,你没有使用微积分,你的语言已经有了递归。所以您所写的是一个在scala中对固定点“组合器”的简单定义。很简单,因为作为一个固定点(几乎)直接遵循定义。

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=& gt; 然后

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

Brian McCutchon 6 年前

首先,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))

因为它是递归的,所以我们需要添加一个返回类型:

定义Y[A,B](F:(A=>B)=>A=>B):A=>B=F(Y(F))