相互递归数据类型

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)