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

Question

В Haskell вы можете сделать следующее:

Prelude> data Foo = Foo Bar; data Bar = Bar Foo 

Как вы можете сделать то же самое в OCaml? Я пробовал:

    ___ 
# type foo = Foo of bar;; type bar = Bar of foo;; 
Error: Unbound type constructor bar 

Возможно ли даже определить взаимно-рекурсивные типы данных в OCaml? Если нет, то почему?

Сравнение определений данных, позволяющих выражениям: взаимно-рекурсивные типы данных соответствуют использованию let rec (или более подходящим образом type rec за отсутствием лучшей фразы). Каковы преимущества возможности определения взаимно-рекурсивных типов данных? Мой пример foobar тривиален. Можете ли вы придумать какие-либо нетривиальные виды использования взаимно-рекурсивных типов данных?

Answer 1

ivg ответил на ваш вопрос, но вот нетривиальным взаимно рекурсивный тип.

module Stream = struct 

    type 'a t = unit -> 'a node 
    and 'a node = Nil 
       | Cons of 'a * 'a t 

end 

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

type 'a t = Stream of (unit -> ('a * 'a t) option) 

Навскидку моя мысль в том, что вы всегда можете уменьшить семейство взаимно рекурсивных типов в один, если вам нравится (хотя, возможно, не в OCaml-кодирования I думая о том, что будет делать нетривиальное использование индексов зависимого типа), но это, безусловно, может быть более ясным.

Answer 2

Использование and

type foo = Foo of bar 
and bar = Bar of foo