Haskell中f x = f x的类型有何正当理由？

Question

Haskell将f x = f x的类型定义为t1 -> t，但是有人能解释一下为什么吗？

此外，是否可能存在其他不等价的函数具有相同的类型？

- TaslemGuy

---

f x = f x 不是一种类型。也许你能解释一下是什么产生了这个“理由”？是 Djinn 吗？是的，其他“函数”有可能拥有相同的类型（任何产生底部的东西都可以，比如 error）。 - Thomas M. DuBuisson

Answer 1

从函数定义 f x = f x 开始，让我们逐步分析并推断出 f 的类型。

首先，我们从一个完全未指定的类型变量 a 开始。我们能否推断出更多信息呢？是的，我们观察到 f 是一个接受一个参数的函数，因此我们可以将 a 转换为两个未知类型变量之间的函数，我们称之为 b -> c。无论 b 代表什么类型，它都是参数 x 的类型，并且无论 c 代表什么类型，它都必须是定义右侧的类型。

那么我们能对右侧推断出什么？嗯，我们有 f，它是对正在定义的函数的递归引用，所以其类型仍然是 b ->c，其中两个类型变量与 f 的定义相同。我们还有 x，它是在定义 f 内部绑定的变量，其类型为 b。应用 f 到 x 进行类型检查是合法的，因为它们共享相同的未知类型 b，结果为 c。

此时，所有的部分都能够拼合在一起，并且没有其他限制，我们可以将类型变量“正式化”，得到一个最终类型 b -> c，其中两个变量是 Haskell 中隐含的普遍量化类型变量。

换句话说，f 是一个接受任何类型的参数并返回任何类型值的函数。它怎么可能返回任何可能的类型呢？其实它不能，我们可以观察到对它进行求值只会产生无限递归。

出于同样的原因，任何具有相同类型的函数在评估时也永远不会返回。

甚至更直接的版本是完全删除参数：

foo :: a
foo = foo

它也是普遍量词，代表任何类型的值。这基本等价于undefined。

- C. A. McCann

---

foo 不等于 undefined。foo 已定义，undefined 未定义：undefined|False=undefined - comonad

Answer 2

f x = undefined

具有(alpha)等效类型f :: t -> a。

---

如果你好奇，Haskell的类型系统是从Hindley-Milner演变而来的。非正式地说，类型检查器为每个东西开始时都具有最宽松的类型，并统一各种约束条件，直到剩下的内容是一致的（或不一致）。在这种情况下，最普遍的类型是f :: t1 -> t，没有其他的约束条件。

相比之下：

f x = f (f x)

由于在左侧将 f 的参数类型与外部 f 的参数类型统一，推断出类型为 f :: t -> t。

- ephemient