f# - 递归调用的函数类型推断

Question

我正在尝试实现一种自定义语言，该语言允许从其最后一条语句中推断出函数返回类型。但是，当找到直接或间接递归函数调用时，类型推断系统显然会失败。

func factorial(a:int) -> 
    if a == 0
        1
    else
        a * factorial(a - 1)

例如，即使参数类型未指定，F# 也会这样做：

let rec fact i =
    if i = 0 then 1 else i * fact (i-1)

这个系统是如何工作的？

Answer 1

F# 类型检查器使用Damas-Hindley-Milner类型推断算法。阶乘的例子可以大致解释如下：

• 从 的声明中fact，我们在表单中得到了它的类型，tx -> ty其中tx = t(i)的t(i)类型是一个值i。

• 从等式检查，因为val (=): 'T -> 'T -> bool我们也有t(i) = t(0) = int.

• 从then分支，我们得到另一个约束ty = t(1) = int。
• 从else分支，普通(*)运算符是'T -> 'T -> 'T这样我们得到t(i) = ty.

基于一组约束：

tx = t(i)
t(i) = t(0) = int
ty = t(1) = int
t(i) = ty

使用统一，我们得出tx = ty = int并推断出factas的类型int -> int。这也意味着如果您更改子句的顺序if/then/else（通过反转条件），类型推断仍然可以正常工作。

也就是说，这是类型推断算法的一个非常简单的示例。您可以按照上面的 Wikipedia 链接阅读更多相关信息。

为了将该算法应用于您的自定义语言，您可以在各种函数式编程书籍中找到实现。有关更多详细信息，请参阅此线程Damas-Hindley-Milner 类型推理算法实现。