指向 OCaml 中记录的指针

Pointer to a record in OCaml

我正在 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 数据类型来实现这一点?

非常感谢。

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

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

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

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

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

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

type tBST = node option

node option 类型的值是 NoneSome n,其中 n 是指向 node 类型值的指针。您将 tBST 用于可变字段(记录 node),因此您将有效地拥有指向节点的可变 C 样式指针。

这可能是您的想法:

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,它没有运行时开销。