Взаимно рекурсивные типы данных

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

UPDATE 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 

Выражение, которое покажет вам, какой узел «п», на основе последнее обновление на ваш вопрос.

(* 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)