OCaml 中的循环映射

Question

我正在尝试构建递归数据结构，但遇到了一些问题。我目前正在实现一个类型系统，并且正在尝试实现递归类型。所以，我想要使用 OCaml 的类型构造函数来拥有实际的无限类型结构，它可以递归。这是我在错误仍在发生的情况下尽可能减少问题的尝试。

module StringMap = Map.Make(String)

type ty = 
  | TyRecord of (ty StringMap.t)

let rec recursive_ty =
  let rec temp = lazy (
    TyRecord (StringMap.singleton "self" (Lazy.force temp))
  ) in
  Lazy.force temp

执行recursive_ty的表达式时出现错误Exception: CamlinternalLazy.Undefined。

基本上，我正在尝试构建一个循环 ty StringMap.t。我希望能够在不启用 -rectypes 的情况下执行此操作 ，特别是因为 recursive_ty 的类型不是递归的，它应该只是 ty。我知道以下工作正常：

type ty = | TyRecord of (string * ty) list let rec recursive_ty = TyRecord [("self", recursive_ty)]

但我想使用 StringMap 来有效地搜索键。任何帮助将不胜感激。

Answer 1

你必须让构造函数变得惰性，例如，

type ty = TyRecord of ty StringMap.t Lazy.t
let rec t = TyRecord (lazy (StringMap.singleton "self" t));;

或者，您可以使用 thunk。

OCaml 中的循环映射

Cyclic Map in OCaml

ocaml

lazy-evaluation

recursive-datastructures