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表达式进行比较:相互递归的数据类型对应于使用let rec(或者更适合type rec于缺少更好的短语).能够定义相互递归数据类型的优点是什么？我的foobar例子是微不足道的.您能想到相互递归数据类型的任何非平凡用法吗？

Answer 1

使用 and

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

它实际上比完全明确的略微烦人.什么是最明确的将是`type rec foo = Foo of bar and bar = Bar of foo`.例如,当你有一个环境类型`t`并且你想在一个子模块中创建一个新类型`t`时会遇到(小)问题,这个子模块将环境`t`别名,但是`type t module X = struct type t = t end`是一个错误,因为它假设你的意思是构造无限类型`type x = x`. (2认同)

Answer 2

ivg回答了你的问题，但这是一个不平凡的相互递归类型。

\n\n\n\n

module Stream = struct\n\n  type \'a t    = unit -> \'a node\n   and \'a node = Nil\n               | Cons of \'a * \'a t \n\nend\n

这是真正类型的脊柱惰性流。也就是说，您可以在没有相互递归类型的情况下构造它

\n\n

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

我的临时想法是，如果您愿意，您总是可以将一系列相互递归的类型减少为单个类型（尽管可能不在 OCaml\xe2\x80\x94 中，我正在考虑的编码将非常重要地使用依赖类型指数），但肯定可以直接更清楚。

\n