Почему мое определение типа отклонено как циклическое, если оно объявлено как вариант, но принято иначе?

Question

я бездельничал с использованием OCaml реализации некоторых структур данных в чисто функциональных структурах данных Криса Окасаки и наткнулся на этом определении типа:

type tree = Node of int * int * tree list;; 

Я не думаю, что он нужен тег, как это не было тип союза, поэтому я попытался устранением тега, однако я получил следующее сообщение об ошибке:

# type tree = int * int * tree list;; 
Characters 5-33: 
type tree = int * int * tree list;; 
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
Error: The type abbreviation tree is cyclic 

Почему это происходит с двумя определениями, казалось бы, эквивалентными типа?

Answer 1

В ML-подобных языках определение рекурсивного типа является тем, где рекурсия не проходит через вариантный тип. Это прагматическое определение в том смысле, что оно ведет к более удобной проверке типов.

В рекурсивных типах нет ничего сложного. Вы можете включить поддержку рекурсивных типов в OCaml с флагом -rectypes.

$ ocaml -rectypes 
     OCaml version 4.02.1 

# type tree = int * int * tree list;; 
type tree = int * int * tree list 
# let x: tree = (3, 3, [(4, 4, [])]);; 
val x : tree = (3, 3, [(4, 4, [])]) 

Все обычные надежные гарантии на печать присутствуют, когда включены рекурсивные типы. Основной недостаток заключается в том, что многие непреднамеренные программы принимаются. Другими словами, наличие рекурсивного типа часто является признаком ошибки программирования.

Answer 2

Определение первого типа определяет новый тип. Когда вы опускаете имя конструктора, вместо того, чтобы определять новый тип, вы фактически вводите аббревиатуру типа. И по умолчанию аббревиатуры типа не могут быть рекурсивными, так как обычно это не то, что вы имеете в виду.

Вы можете использовать любой синтаксис определения типа, который определяет новый тип для создания рекурсивных типов, а не только вариантов. Записи будут работать также, например

type tree = { node : int * int * tree list } 

или даже лучше

type tree = { 
    value : int; 
    depth : int; 
    children : tree list; 
} 

(примечание: имена полей были выбраны произвольно, как я не знаю их первоначальное назначение)

Подводя итог, сумма типы используются не только для введения непересекающихся наборов типов, но и для создания новых типов:

type t = Constr x 

вводит тип t, который может быть сконструирован с помощью конструктора Constr от значений типа x.