OCaml中的递归函数子是什么？

Question

这个问题类似于这一个，但我想声明一个递归的functor而不是递归的module。所以我有：

一个接口A：

module type A = sig
    type t
    val basic_func: ...
    val complex_func: ...
end

一个实现了 A.complex_func 的函数对象 ComplexImpl，其基于 A.basic_func 实现：

module ComplexImpl (SomeA : A) =
struct
    let complex_impl params =
        SomeA.basic_func ...
        ...
end

另一个接口I：

module type I = sig
    type t
    ...
end

还有一个函数对象B，它接受类型为I的参数，实现接口A并使用ComplexImpl来实现complex_func。我想写出这样的代码：

(* I can't write 'rec' here *)
module rec B (SomeI : I) :
    A with type t = SomeI.t
= struct
    type t = SomeI.t
    (* this line does not work *)
    module Impl = ComplexImpl(B(I))

    let basic_func (x : t) = ...
    let complex_func (x : t) =
        Impl.complex_impl x
end

但是我无法声明一个递归函数对象...

---

我找到的实现递归函数对象的唯一方法是将它自己作为参数：

module B (SomeI : I) (CopyOfB : A with type t = SomeI.t) :
    A with type t = SomeI.t
= struct
    type t = SomeI.t
    (* this line works *)
    module Impl = ComplexImpl(CopyOfB)

    let basic_func (x : t) = ...
    let complex_func (x : t) =
        Impl.complex_impl x
end

然后像这样使用：

module rec RealB = B(SomeI)(RealB)

但是语法冗长，不太安全（如果有人输入与RealB不同的参数会怎样），如果RealB本身是一个函数符号，则变得非常棘手...

- Steakfly

Answer 1

递归模块必须具有以下形式的语法限制：

module rec Name : module_type = module_expr

这意味着递归函数对象不能使用以下方式声明：

module rec Name (Arg : module_type) : module_type = module_expr

但必须写成：

module rec Name : functor (Arg : module_type) -> module_type =
  functor (Arg : module_type) -> module_expr

- Leo White

---

然而，在我的情况下，这并不起作用，因为 B(SomeI) 的签名是 A with type t = SomeI.t。因此，按照您的术语，Name 的 module_type 取决于 Arg，这是无效的（除非我漏掉了什么）。 - Steakfly

在你的情况下它可以正常工作。Name 的 module_type 也将采用 functor (Arg : modtype) -> modtype 的形式（因为 Name 的类型是一个函数子类型）。我会更新我的答案以使其更清晰明了。 - Leo White

在我的情况下，我会得到以下错误：无法安全地评估递归定义模块B的定义。 - Steakfly

你的代码不一定是良好的，因为B(SomeI)的定义涉及到调用B(SomeI)。在你提出的问题解决方案中，你利用了OCaml提供的一个解决方法——如果一个模块只包含函数，则它允许潜在的不良基础递归（如果实际上是不良基础递归，则会在运行时引发异常）。这个解决方法对于函数子也不受支持。 - Leo White

个人而言，如果可能的话，我会避免使用递归模块。有时候是不可避免的，但通常有一种更简单的方法可以避免使用它们。 - Leo White

Answer 2

我找到了一个解决方案:

module B (SomeI : I) = struct
    (* introduce a recursive module Implementation *)
    module rec Implementation :
        A with type t = SomeI.t
    = struct
        type t = SomeI.t
        (* use Implementation here *)
        module Impl = ComplexImpl(Implementation)

        let basic_func (x : t) = ...
        let complex_func (x : t) =
            Impl.complex_impl x
    end

    (* include the code of Implementation here *)
    include Implementation
end

我可以像这样使用它：

module RealB = B(SomeI)

- Steakfly

---

这仅在函数对象实际上不是递归的情况下才有效，但它的结果是递归的。Leo展示的通用解决方案允许函数对象应用于自身，即使使用不同的参数也可以。 - Andreas Rossberg