相互遞歸數據類型

Question

我正在嘗試創建一對相互遞歸的數據類型來表示OCaml中用於作業分配的紅黑樹。但是，我對OCaml語言非常不熟悉，所以我有一些語法問題。

這裏就是我來了這麼遠：

type 'a red_black_tree = 
| RedNode of 'a * ('a black_node * 'a black_node) 
| BlackNode of 'a black_node 
and 'a black_node = 
| TwoRedNodes of 'a * ('a RedNode * 'a RedNode) 
| TwoBlackNodes of 'a * ('a black_node * 'a black_node) 
| BlackLeaf;; 

當我輸入到這一點的OCaml它給了我：

utop # type 'a red_black_tree = 
| RedNode of 'a * ('a black_node * 'a black_node) 
| BlackNode of 'a black_node 
and 'a black_node = 
| TwoRedNodes of 'a * ('a RedNode * 'a RedNode) 
| TwoBlackNodes of 'a * ('a black_node * 'a black_node) 
| BlackLeaf;; 
Error: Syntax error 

您不能引用類型的子值從一個子類？沒有尋找問題的實際答案，只是語法澄清。

UPDATE

我有這個最初的嘗試之後，但它是由教授說，這是不是一個對相互遞歸的數據類型的：

type 'a red_black_tree = 
| RedNode of 'a red_node 
| BlackNode of 'a black_node 
and 'a red_node = 
| RedTree of 'a * ('a black_node * 'a black_node) 
and 'a black_node = 
| TwoRedNodes of 'a * ('a red_node * 'a red_node) 
| TwoBlackNodes of 'a * ('a black_node * 'a black_node) 
| BlackLeaf;; 

更新2

問題3 紅黑樹是一種有時用來組織數值數據的樹。它有兩種類型的節點，黑節點和紅節點。紅色節點總是有一個數據和兩個孩子，每個孩子都是一個黑色節點。黑色節點可能有：1）一塊數據和兩個子節點是紅色節點; 2）一個數據和兩個黑人節點的孩子;或3）沒有數據和沒有孩子（即葉節點）。 （這不是紅黑樹的精確描述，但是適用於此練習。）

編寫一對相互遞歸的OCaml數據類型，它們表示紅黑樹中的紅色節點和黑色節點。數據應該能夠具有任何類型，也就是說，您的類型應該是存儲在樹中的數據類型中的多態。

Answer 1

最終，一對相互遞歸的數據類型爲紅黑樹的實施是：

type ’a black_node = Leaf 
| RNode of ’a * ’a red_node * ’a red_node 
| BNode of ’a * ’a black_node * ’a black_node 
and ’a red_node = RedNode of ’a * ’a black_node * ’a black_node;; 

Answer 2

這是一個錯誤：

| TwoRedNodes of 'a * ('a RedNode * 'a RedNode) 
          ^^^^^^^  ^^^^^^^ 

這裏RedNode應該是型構造，而不是一個值構造。我懷疑，那你要增加一個類型'a red_node，並定義TwoRedNodes分支如下：

| TwoRedNodes of 'a * ('a red_node * 'a red_node) 

Answer 3

type 'a red_node = 'a * ('a black_node * 'a black_node) 
and 'a black_node = ('a * ('a node * 'a node)) option 
and 'a node = 
    Red of 'a red_node 
    | Black of 'a black_node 

的表達，會告訴你「N」的基礎上，什麼樣的節點最後更新你的問題。

(* to determine if a black node is a type 1 black node *) 
match n with 
| Black n' -> 
    begin match n' with 
    | Some n'' -> 
     begin match n'' with 
     | _, (Red _, Red _) -> "type 1 black node" 
     | _, (Black _, Black _) -> "type 2 black node" 
     | _ -> raise (Failure "invalid node") 
     end 
    | None -> "leaf node" 
    end 
| Red _ -> "red node";; 

在類型OCaml中的語義：OCaml中A型名稱必須以一個小寫字母（例如list，array，ref）開始，但類型構造必須用大寫字母（例如Some）開始。這個類型是一個包含所有構造函數的傘。

P.S .:我不認爲你甚至需要這個問題的相互遞歸數據類型。下面應該工作：

type 'a node = 
    Red of 'a * ('a node * 'a node) 
    | Black of 'a option * ('a node option * 'a node option)