haskell - 相互递归函数的 Hindley Milner 类型推断

Question

我正在制作一种强类型玩具函数式编程语言。它使用 Hindley Milner 算法作为类型推断算法。

实现该算法，我有一个关于如何推断相互递归函数的类型的问题。

let rec f n = if n == 0 then 0 else g (n - 1)
let rec g n = if n == 0 then 0 else f (n - 1)

f并且g是相互递归的函数。现在，当类型检查器推断 function 的类型时f，它也应该能够推断 function 的类型g，因为它是一个子表达式。

但是，在那一刻，功能g还没有定义。因此，类型检查器显然甚至不知道 function 的存在以及 functiong的类型g。

现实世界的编译器/解释器使用哪些解决方案？

Answer 1

在 OCaml 中，相互递归的值由关键字and而不是 another分隔let rec。当打字系统到达递归定义时，它将所有递归名称添加到环境中，然后像往常一样继续。

更新（感谢 KA Buhr）：

完全有可能创建一个具有类型'a（'a新鲜）的新变量，然后再统一它。一定要在正确的地方概括你的变量（通常是在定义之后）。