为什么这个函数的类型是(a -> a) -> a？
Prelude> let y f = f (y f)
Prelude> :t y
y :: (t -> t) -> t
它不应该是无限/递归类型吗？我打算尝试用文字表达我认为它应该是什么类型，但由于某种原因我无法做到。
y :: (t -> t) -> ?WTFIsGoingOnOnTheRHS?
我不明白 f (yf) 如何解析为一个值。以下对我来说更有意义：
Prelude> let y f x = f (y f) x
Prelude> :t y
y :: ((a -> b) -> a -> b) -> a -> b
但这仍然令人困惑。这是怎么回事？
好吧，对于某些人来说，必须是 type ，我们y还不知道；毕竟，它接受一个函数，并将其应用于一个参数，所以它必须是一个接受一个函数的函数。(a -> b) -> cabcf
因为y f = f x（再次，对于 some x），我们知道 的返回类型y必须是f自身的返回类型。所以，我们可以细化y一点的类型：它一定是(a -> b) -> b针对一些我们还不知道的a。b
要弄清楚是什么a，我们只需要查看传递给的值的类型f。它是y f，这是我们现在试图找出类型的表达式。我们说 of 的类型y是(a -> b) -> b（对于某些a,b等），所以我们可以说这个应用程序 ofy f必须是类型b本身。
所以，参数的类型f是b。将它们重新组合在一起，我们就得到(b -> b) -> b了——当然，这与(a -> a) -> a.
这是一个更直观但不太精确的事物视图：我们说的是y f = f (y f)，我们可以将其扩展为等价的y f = f (f (y f)), y f = f (f (f (y f)))，等等。因此，我们知道我们总是可以f在整个事物周围应用另一个，并且由于所讨论的“整个事物”是应用于f参数的结果，f因此必须具有 type a -> a; 并且由于我们刚刚得出结论，整个事情是应用于f参数的结果，所以返回类型y必须是它f自己的类型——再次组合在一起，如(a -> a) -> a.
只有两点可以添加到其他人的答案中。
您定义的函数通常称为fix，它是定点组合器：计算另一个函数的不动点的函数。在数学中，函数的不动点f是一个参数x，使得f x = x. 这已经允许您推断出的类型fix必须是(a -> a) -> a; a“从to获取函数a并返回. 的函数a。”
您已经调用了您的函数y，它似乎在Y 组合器之后，但这是一个不准确的名称：Y 组合器是一种特定的定点组合器，但与您在此处定义的不同。
我不明白 f (yf) 如何解析为一个值。
好吧，诀窍在于 Haskell 是一种非严格（又名“惰性”）语言。如果不需要在所有情况下评估其参数，则计算f (y f)可以终止。因此，如果您要定义阶乘（如 John L 所示），则评估为 1 而无需评估。fy ffac (y fac) 1y fac
严格的语言无法做到这一点，因此在这些语言中，您不能以这种方式定义定点组合子。在这些语言中，教科书的定点组合器是正确的 Y 组合器。
@ehird 很好地解释了类型，所以我想通过一些示例来展示它如何解析为一个值。
f1 :: Int -> Int
f1 _ = 5
-- expansion of y applied to f1
y f1
f1 (y f1) -- definition of y
5 -- definition of f1 (the argument is ignored)
-- here's an example that uses the argument, a factorial function
fac :: (Int -> Int) -> (Int -> Int)
fac next 1 = 1
fac next n = n * next (n-1)
y fac :: Int -> Int
fac (y fac) -- def. of y
-- at this point, further evaluation requires the next argument
-- so let's try 3
fac (y fac) 3 :: Int
3 * (y fac) 2 -- def. of fac
3 * (fac (y fac) 2) -- def. of y
3 * (2 * (y fac) 1) -- def. of fac
3 * (2 * (fac (y fac) 1) -- def. of y
3 * (2 * 1) -- def. of fac
您可以使用任何您喜欢的功能按照相同的步骤来查看会发生什么。这两个例子都收敛到值，但这并不总是发生。
让我谈谈一个组合器。它被称为“定点组合器”，它具有以下属性：
属性：“定点组合器”接受一个函数f :: (a -> a)并发现该函数的“定点” x :: a，使得f x == x. 固定点组合器的某些实现在“发现”方面可能更好或更差，但假设它终止，它将产生输入函数的固定点。任何满足该属性的函数都可以称为“定点组合器”。
将此称为“定点组合器” y。根据我们刚才所说，以下情况属实：
-- as we said, y's input is f :: a -> a, and its output is x :: a, therefore
y :: (a -> a) -> a
-- let x be the fixed point discovered by applying f to y
y f == x -- because y discovers x, a fixed point of f, per The Property
f x == x -- the behavior of a fixed point, per The Property
-- now, per substitution of "x" with "f x" in "y f == x"
y f == f x
-- again, per substitution of "x" with "y f" in the previous line
y f == f (y f)
所以你去。您已经根据定点组合器的基本属性定义 了： . 您可以假设表示发散的计算，而不是假设发现，并且仍然得出相同的结论（iinm）。y
y f == f (y f)y fxx
由于您的函数满足 The Property，因此我们可以得出结论，它是一个定点组合子，并且我们已经说明的其他属性（包括类型）适用于您的函数。
这并不是一个可靠的证据，但我希望它能提供更多的见解。