递归模块中的 OCaml 类型绑定

Question

我正在尝试在 ocaml 中构建一系列递归模块。这是一个最简单的例子：

  module rec Foo : sig
    type t =
      | A of int
      | B of Foo.t
  end = struct
    type t =
      | A of int
      | B of Foo.t
  end       

  module rec Bar : sig
    open Foo
    type map_t = int -> Foo.t
    type t = { foo : map_t }
    val bar_of_foo : Foo.t -> t
  end = struct
    open Foo

    let rec bar_of_foo f = match f with
      | A a -> let ff (_:int) = a in 
               { Bar.foo = ff }
      | B b -> { foo = bar_of_foo b.foo } 
  end

在 A 与 Error: unbound type constructor f 的匹配中，函数 bar_of_foo 编译失败。

我不明白为什么会这样 - 字段 foo 被定义为具有类型 map_t = int -> Foo.t，并且 f 具有签名 int -> Foo.t.

我也试过简单地将记录字段 foo 称为 foo 而不是 Bar.foo （在 B 的匹配情况下 - 这给了我一个 Errror: unbound record field foo错误）。

非常感谢收到任何指示或建议。

史蒂夫

Answer 1

这个答案现在是多余的，因为这里指出的事情反映在问题中。

您的记录表达式中存在语法错误。使用 = 而不是 :，即 { Bar.foo = f } 和 { foo = bar_of_foo b }。

在那之后，您的代码仍然存在一些输入问题。例如，bar_of_foo b 的类型为 t，因此它不能用作 t 的 foo 成员。

Answer 2

因为 bar_of_foo 是一个函数，它的类型是 x -> y。
类型推断算法发现您在 Foo.t 的构造函数上对参数 f 进行了模式匹配。这个事实修复了 x = Foo.t。
当您 return {foo = ...} 时，系统得到 y = Bar.t（或者在我们的上下文中只是 t）。
所以，bar_of_foo : Foo.t -> Bar.t.

以下代码可以编译，它与 OP 中的代码类似：

module Foo : sig
  type t =
  | A of int
  | B of t
  end = struct
  type t =
      | A of int
      | B of t
  end

module Bar : sig
  type map_t = int -> Foo.t
  type t = { foo : map_t }
  val bar_of_foo : Foo.t -> t
  end = struct
    open Foo

    type map_t = int -> Foo.t
    type t = { foo : map_t }

    let rec bar_of_foo f = match f with
      | A a -> { foo = fun (_:int) -> A a }
      | B b -> bar_of_foo b 
  end

一个测试：

open Foo
open Bar

let () =
  let bar = bar_of_foo (B (B (B (A 42)))) in
  match (bar.foo 0) with
    | A n -> print_int n; print_newline ()
    | B _ -> print_string "Impossible!\n"

并且输出：

$ ocaml example.ml
$ 42

请注意模块 Foo 和 Bar 不是相互递归的。否则我们将不得不写

module rec Foo : sig
  ...
  end = struct
  ...
  end
and Bar : sig
  ...
  end = struct
    ... 
  end

递归模块中的 OCaml 类型绑定

OCaml type binding in recursive modules

ocaml