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

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

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)

这个系统是如何工作的？

最佳答案

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 并将 fact 的类型推断为 int -> int 。这也意味着如果您更改 if/then/else 中子句的顺序(通过反转条件)，类型推断仍然可以正常工作。

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

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

关于f# - 具有递归调用的函数类型推断，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15428037/