我正在制作一种强类型玩具函数式编程语言。它使用 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
的类型。
现实世界的编译器/解释器使用哪些解决方案?
最佳答案
在 OCaml 中,相互递归的值由关键字 and
分隔,而不是另一个 let rec
。当类型系统到达递归定义时,它将所有递归名称添加到环境中,然后像平常一样继续。
更新(感谢 K.A. Buhr):
完全可以创建一个 'a
类型的新变量('a
是新鲜的),然后统一它。确保在正确的位置概括您的变量(通常在定义之后)。
关于haskell - 相互递归函数的 Hindley Milner 类型推理,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49134312/