带有指针的命令式 OCaml 数据结构？

Question

这样的事情可能吗？

大家好，

在我的 class 中，我们被告知要使用函数式和命令式编程在 OCaml 中实现二叉搜索树。我们正在关注 ADT 和 Pascal 中的实现，Pascal 是一种使用指针的过程语言。

数据结构如下所示：

# Pascal
type
   tKey      = integer;
   tPos      = ^tNode;
   tNode     = record
          key         : tKey;
          left, right : tPos;
           end;      
   tBST = tPosT;

我们还学习了一些基本的 BST 操作。这是其中的一个例子，如果这对您有帮助的话：

# Pascal
procedure add_key(VAR T : tBST; k:tKey);
var new, parent, child :  tBST;
begin
   createNode(new);
   new^.key := k;
   new^.left := nil;
   new^.right := nil;

   if T=nil then
      T := new
   else begin
      parent := nil;
      child := T;
      while (child <> nil) and (child^.key <> k) do begin
     parent := child;
     if k < child^.key then
        child := child^.left
     else
        child := child^.right;
      end;

      if (child = nil) then 
     if k < parent^.key then
        parent^.left := new
     else
        parent^.right := new;
        { duplicates are ignored }
   end;
end;

这就是我的功能（如果有意义的话）数据结构的样子：

type key =
    Key of int;;

type bst = 
    Empty   
    | Node of (key * bst * bst);;

但是，我在使用 OCaml 的命令式方面遇到了很大的麻烦。我必须让它看起来尽可能与 Pascal 实现相似，而且我不知道 OCaml 中数据结构和指针的可能性，因为我一直使用递归等进行编程。我正在考虑使用多个 "let"、if 和 else，但我不知道如何定义我的数据结构。将不胜感激。

Answer 1

据我了解，您的类型应该是这样的：

type key = int

type t = Empty | Node of t * key * t

但是你的添加函数不应该是这样的:

let rec add x t =
  match t with
    | Empty ->
      Node (Empty, x, Empty)
    | Node (l, v, r) ->
      let c = compare x v in
      if c = 0 then t
      else if c < 0 then Node (add x l, v, r)
      else Node (l, v, add x r)

因为这只是功能性的。

也许您可以将类型更改为：

type t = Empty | Node of t ref * key * t ref

并尝试使 add 函数适应这种类型。

带有指针的命令式 OCaml 数据结构？

Imperative OCaml data structure with pointers?

ocaml

pointers

imperative

abstract-data-type