编码为模块递归的多态递归的类型推断
Type inference for polymorphic recursion encoded as module recursion
标准 ML 没有多态递归。将递归添加到模块语言允许我们恢复多态递归作为一种特殊情况，使用 endofunctors 的不动点。例如：
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)
众所周知，多态递归使类型推断变得不可判定。但是，函子定义已经包含部分类型信息，即其参数的签名。此信息是否足以使类型推断再次可判定？
是的，因为签名提供了一个"forward declaration"的多态类型，所以不用递归推断。另外，你不需要仿函数，你可以直接写一个递归结构绑定。但这需要签名注释，因此效果相同。
标准 ML 没有多态递归。将递归添加到模块语言允许我们恢复多态递归作为一种特殊情况，使用 endofunctors 的不动点。例如：
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)
众所周知，多态递归使类型推断变得不可判定。但是，函子定义已经包含部分类型信息，即其参数的签名。此信息是否足以使类型推断再次可判定？
是的，因为签名提供了一个"forward declaration"的多态类型，所以不用递归推断。另外，你不需要仿函数，你可以直接写一个递归结构绑定。但这需要签名注释，因此效果相同。