我正在尝试使用基于 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 进行不同的替换)。
我如何推断这些类型？
最佳答案
在您的情况下，您需要推断 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 中，可怕的单态限制使这变得更加复杂，但如果我们没有类型类，我们可以忽略它。)
关于haskell - 如何推断递归函数的类型？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67254536/