命令型ポインタによるOCamlのデータ構造

Question

このようなことは可能ですか？

こんにちはすべて、私たちは、機能と命令型プログラミングを使用して、OCamlの中でバイナリ検索ツリーを実装するように言われた私のクラスで

。 ポインタを使用する手続き型言語であるパスカル（Pascal）でADTと実装を行っています。我々はまた、いくつかの基本的なBST業務を与えられた

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

：

これは、データ構造がどのように見えるかです。それが役立つことができればここでは、1の例である：

# 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機能を適応してみてください。