recursion - 这个函数的类型是如何推断的？

Question

我挠头想弄清楚这个函数的签名

let make_rec f_norec =
  let rec f x = f_norec f x in
  f

应该是

val make_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>.

注意有一个奇怪的递归定义。肯定我错过了一些知识。谁能告诉我如何计算函数的类型（就像类型推断系统一样）？

太谢谢了。

Answer 1

从内部开始，向外工作：

1. 让我们称之为类型x a
2. 然后f有类型a -> b，其中b的结果类型是f
3. f_norec接受fandx并且它必须返回与 相同的类型f，因此(a->b) -> a -> b
4. make_rec接受f_norec，然后返回f。因此((a->b)->a->b) -> (a->b)。出于语法原因，可以省略最后一对括号。