在Haskell(GHC)中使用什么算法来导出递归表达式的类型？

Question

请考虑以下示例:

非递归函数

 f x = x
 g y = f 'A'

GHC推断 f :: a -> a

相互递归函数

 f x = const x g
 g y = f 'A'

现在GHC推断f :: Char -> Char,即使类型可能a -> a只是在前一种情况下.

多态递归

 data FullTree a = Leaf | Bin a (FullTree (a, a))

 size :: FullTree a -> Int
 size Leaf = 0
 size (Bin _ t) = 1 + 2 * size t

size除非给出明确的类型,否则GHC无法推断出类型.

---

因此,看起来Haskell(GHC)不使用多态递归(如Alan Mycroft中描述的:多态类型方案和递归定义),因为它不能推断示例2和3中的多态类型.但在第一种情况下它正确推断最常见的类型f.什么是确切的程序？是否GHC分析表达式,组织它们的依赖一起(类似f与g在第二个例子),并在这些团体使用单态递归类型推断？

Answer 1

GHC是否分析表达式的依赖关系,将它们组合在一起(如第二个例子中的f和g),并对这些组使用单态递归类型推断？

是的,确实如此.Haskell 2010报告有一个关于该主题的部分.