如何推断递归函数的类型？
How can I infer types for recursive functions?
我正在尝试使用基于 Hindley-Milner 算法的类型推断来实现语言。但是我不知道如何推断递归函数的类型：
f = g
g = f
这里我必须同时生成和求解 f 和 g 的约束，因为如果我早点对一个函数执行此操作，它将不知道另一个函数的类型。但是我不能同时对模块中的所有函数执行此操作：
f = h 0
g = h "str"
h _ = 0
在f中我有h :: Int -> Int，在g中我有h :: String -> Int，如果我同时解决它会产生错误但不会如果我将在 f 和 g 的类型之前推断 h 的类型（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 中，可怕的单态限制使这变得更加复杂，但如果我们没有类型 类，我们可以忽略它。）
我正在尝试使用基于 Hindley-Milner 算法的类型推断来实现语言。但是我不知道如何推断递归函数的类型：
f = g
g = f
这里我必须同时生成和求解 f 和 g 的约束，因为如果我早点对一个函数执行此操作，它将不知道另一个函数的类型。但是我不能同时对模块中的所有函数执行此操作：
f = h 0
g = h "str"
h _ = 0
在f中我有h :: Int -> Int，在g中我有h :: String -> Int，如果我同时解决它会产生错误但不会如果我将在 f 和 g 的类型之前推断 h 的类型（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 中，可怕的单态限制使这变得更加复杂，但如果我们没有类型 类，我们可以忽略它。）