我想详细了解一下我们是如何从 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的返回类型？
首先，Scala 代码的编写方式很长：
def Y[A, B](f: (A => B) => A => B): A => B = f(Y(f))
在这里，f被部分应用。（看起来代码作者选择使用 lambda 来使其更明确。）
现在，我们如何得到这个代码？维基百科指出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))
请注意，您编写的不是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 => Bthen的输入
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