指向 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
类型的值是 None
或 Some 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,它没有运行时开销。
我正在 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
类型的值是 None
或 Some 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,它没有运行时开销。