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 是相互递归函数。现在，当类型检查器推断函数 f 的类型时，它也应该能够推断函数 g 的类型，因为它是一个子表达式。

但是，在那一刻，函数g还没有定义。因此，类型检查器显然不知道函数 g 的存在，也不知道函数 g 的类型。

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

Answer 1

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

更新(感谢 K.A. Buhr):

完全可以创建一个 'a 类型的新变量('a 是新鲜的)，然后统一它。确保在正确的位置概括您的变量(通常在定义之后)。