编码为模块递归的多态递归的类型推断

Question

标准ML不具有多态递归。将递归添加到模块语言中，允许我们使用内函子的固定点，将多态递归作为一种特殊情况来恢复。例如:

signature SEQ =
sig
  type 'a seq
  (* operations on sequences *)
end
functor BootstrapSeq (S : SEQ) =
struct
  datatype 'a seq
    = Nil
    | Zero of ('a * 'a) S.seq
    | One of 'a * ('a * 'a) S.seq
  (* operations on sequences *)
end
structure rec Seq = BootstrapSeq (Seq)

众所周知，多态递归使得类型推断不可确定。然而，函子定义已经包含了部分类型信息，即其实参的签名。这个信息是否足以使类型推断再次确定?

Answer 1

是的，因为签名提供了多态类型的"前向声明"，所以它不需要递归地推断。同样，您不需要函子，您可以直接编写递归结构绑定。但这需要签名注释，因此相当于相同的。