haskell - 为什么这个函数的类型是(a -> a) -> a？

Question

为什么这个函数的类型是(a -> a) -> a？

Prelude> let y f = f (y f)
Prelude> :t y
y :: (t -> t) -> t

它不应该是无限/递归类型吗？我本想尝试用文字表达我认为它应该是什么类型，但由于某种原因我无法做到。

y :: (t -> t) -> ?WTFIsGoingOnOnTheRHS?

我不明白 f (y f) 如何解析为一个值。以下对我来说更有意义:

Prelude> let y f x = f (y f) x
Prelude> :t y
y :: ((a -> b) -> a -> b) -> a -> b

但它仍然令人困惑。这是怎么回事？

Answer 1

嗯，y类型必须为 (a -> b) -> c ，对于某些人a , b和c我们还不知道；毕竟，它需要一个函数，f ，并将其应用于参数，因此它必须是一个带有函数的函数。

自 y f = f x (同样，对于某些 x )，我们知道 y 的返回类型必须是 f 的返回类型本身。所以，我们可以细化 y 的类型一点:一定是(a -> b) -> b对于一些a和b我们还不知道。

弄清楚什么a也就是说，我们只需要查看传递给 f 的值的类型。 。这是y f ，这是我们现在试图找出类型的表达式。我们说的是 y 的类型是 (a -> b) -> b (对于某些 a 、 b 等)，所以我们可以说 y 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必须具有类型 a -> a ;因为我们刚刚得出结论，整个事情都是应用 f 的结果对于参数，返回类型 y必须是f本身 - 再次聚集在一起，如 (a -> a) -> a .