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

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

An expression that will tell you what sort of node 'n' is, based on the last update to your question.

(* 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";;

On the semantics of types in OCaml: A type name in OCaml must always start with a lowercase letter (e.g. list, array, ref), but type constructors must start with uppercase letters (e.g. Some). The type is an umbrella encompassing all its constructors.

P.S.: I don't think you even need mutually recursive data types for this problem. The following should work:

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

Answer 3

this is an error:

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

Here RedNode should be a type constructor, not a value constructor. I suspect, that you're going to add one more type 'a red_node and define your TwoRedNodes branch as follows:

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