相互递归数据类型

Question

我正在尝试创建一对相互递归的数据类型来表示 OCaml 中的 red-black 树以用于家庭作业。但是，我对 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

您不能从子类型引用类型的子值吗？不寻找问题的实际答案只是语法澄清。

更新

我在最初尝试后得到了这个，但教授说它不是对相互递归的数据类型:

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 red-black 树是一种有时用于组织数值数据的树。它有两种类型的节点，黑色节点和红色节点。红色节点总是有一个数据和两个children，每个都是一个黑色节点。黑色节点可能有：1）一条数据和两个children是红色节点； 2）一条数据和两个children是黑节点；或 3) 无数据且无 children（即叶节点）。（这不是 red-black 树的精确描述，但对本练习来说是成功的。）

编写一对相互递归的 OCaml 数据类型，表示 red-black 树中的红色节点和黑色节点。数据应该可以有任何类型，也就是你的类型在树中存储的数据类型应该是多态的。

Answer 1

这是一个错误：

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

这里RedNode应该是type构造函数，不是值构造函数。我怀疑您要再添加一种类型 'a red_node 并按如下方式定义 TwoRedNodes 分支：

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

Answer 2

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 中的类型名称必须始终以小写字母开头（例如 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)

Answer 3

最终，红黑树的一对相互递归数据类型的实现是：

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;;

相互递归数据类型

Mutually recursive datatypes

recursion

ocaml

algebraic-data-types