指向 OCaml 中记录的指针

Question

我正在 OCaml 中实现二叉搜索树，尝试尽可能多地使用命令式编程。

我有以下数据类型：

type tKey = Key of int;;

type tBST = Null | Pos of node ref
            and node = {mutable key : tKey; mutable left : tBST; mutable right : tBST};;

我在使用此功能时遇到问题：

let createNode k tree = 
    tree := Pos ({key = k; left = Null; right = Null});;

Error: This record expression is expected to have type node ref
       The field key does not belong to type ref

二叉搜索树可以是 Null（表示空树）或 Pos。一棵树Pos是指向一个节点的指针，一个节点是一个键和另外2棵树（左和右）的结构。

我这里的主要目标是有一个在函数结束后修改的树。通过引用传递树，所以当 createNode 结束时，我作为参数传递的 tBST 被修改。

问题：我在 OCaml 中尝试做的事情实际上是可能的吗？如果是这样，我该如何更改我的函数 createNode and/or 数据类型来实现这一点？

非常感谢。

Answer 1

可以，但您需要创建 Pos 节点并明确引用：

Pos (ref {key = k; (*...*)})

不过，您尝试做的事情是否被推荐使用像 Ocaml 这样的语言进行练习是另一回事。

Answer 2

问题已经得到解答。我只想添加一个旁注：在这种情况下使用 ref 似乎是多余的。

tBST 类型的值是 Null 或可变指针。如果是 Null，它将保持 Null。如果它是非Null，它将保持非Null，但实际指针可能会改变。这很可能是你想要的，但我有我的怀疑。特别是，tBST 没有做的是模拟 C 风格的指针（它们要么是 null 要么真的指向某处）。不过，我怀疑那是你的意图。

模拟 C 风格指针的惯用方法是只使用内置的 option 类型，如下所示：

type tBST = node option

node option 类型的值是 None 或 Some n，其中 n 是指向 node 类型值的指针。您将 tBST 用于可变字段（记录 node），因此您将有效地拥有指向节点的可变 C 样式指针。

Answer 3

这可能是您的想法：

type tree = node option ref
and node  = {
  mutable left: tree;
  mutable key: int;
  mutable right: tree;
};;

let t0 : tree = ref None;;
let t1 : tree = ref (Some { left = ref None; key = 1; right = ref None; }) ;;

let create_node key tree = 
  tree := Some { left = ref None; key; right = ref None; }

key 不需要单独的类型，但如果需要，您可以，并且使用最新的 OCaml，它没有运行时开销。

指向 OCaml 中记录的指针

Pointer to a record in OCaml

pointers

ocaml

binary-search-tree

record

imperative-programming