haskell - 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 报告有一个关于该主题的部分。