Mutually recursive datatypes

Question

I'm attempting to create a pair of mutually recursive datatypes to represent a red-black tree in OCaml for a homework assignment. However, I'm very unfamiliar with the OCaml language so I'm having some syntactical issues.

Here's what I have come up with so far:

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

When I input this into ocaml it gives me:

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

Are you not able to reference a sub value of a type from a subtype? Not looking for an actual answer to the problem just syntax clarification.

UPDATE

I had this after the initial attempt but it was stated by the professor that it wasn't a pair of mutually recursive datatypes:

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

UPDATE 2

Problem 3 A red-black tree is a kind of tree sometimes used to organize numerical data. It has two types of nodes, black nodes and red nodes. Red nodes always have one piece of data and two children, each of which is a black node. Black nodes may have either: 1) one piece of data and two children that are red nodes; 2) one piece of data and two children that are black nodes; or 3) no data and no children (i.e., a leaf node). (This isn’t a precise description of red-black trees but suces for this exercise.)

Write a pair of mutually recursive OCaml datatypes that represent red nodes and black nodes in red-black trees. The data should be able to have any type, that is, your type should be polymorphic in the kind of data stored in the tree.

Answer 1

Ultimately, the implementation for a pair of mutually recursive datatypes for a red black tree was:

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