haskell - 如何推断递归函数的类型？

Question

我正在尝试使用基于 Hindley-Milner 算法的类型推断来实现语言。但我不知道如何推断递归函数的类型:

f = g
g = f

在这里，我必须为 f 生成并求解约束和 g在一起，因为如果我早点为一个函数做这件事，它就不知道另一个函数的类型。但我不能同时对模块中的所有函数执行此操作:

f = h 0
g = h "str"
h _ = 0

这里是f我有h :: Int -> Int在g我有h :: String -> Int , 如果我同时解决它会产生错误但如果我推断 h 的类型则不会在 f 的类型之前和 g ( h :: forall a. a -> Int 并且可以用在 f 和 g 中，对 a 进行不同的替换)。

我如何推断这些类型？

Answer 1

在您的情况下，您需要推断 h 的类型并将其概括为多类型，然后再推断 f 和 g 的类型.

如果我没记错的话，Haskell 在这种情况下使用的策略是计算依赖图(哪个标识符取决于哪个标识符)，然后将图分离为强连接的组件。这提供了一种定义之间的排序，然后进行相应的处理。

例如，在

f = using1 g h
g = using2 f
h = something

我们有 SCC {h}, {f g}，我们将它们排序为

{h} < {f, g}

因为 SCC {f,g} 依赖于 {h}。然后我们推断出 h 的多类型，并在推断 f 和 g 时使用它。

在一般情况下，我们会在 SCC 之间得到一个偏序，用于驱动拓扑排序算法，该算法在每一步推断类型。

(在 Haskell 中，可怕的单态限制使这变得更加复杂，但如果我们没有类型类，我们可以忽略它。)