types - 什么是相互递归类型？

Question

如果在 ML 中，递归数据类型的示例是：

datatype llist = Nil | Node of int * llist

在 ML 中，什么是相互递归的数据类型以及它的一个例子？

Answer 1

一个这样的例子可能是这些愚蠢的数据类型。

datatype a = A | Ab of b
and      b = B | Ba of a

它们没有任何意义，但它们表明可以使用and关键字（就像函数一样）来引用“提前”的东西，这通常是不可能的

它们是相互的（因为它们都是......）递归的（......相互引用）

Answer 2

相互递归数据类型的标准基本示例是树和森林：森林是树的列表，而树是值和森林（根及其子树的子树的值）。在标准 ML 中，这可以定义如下，允许空树：

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

摘自“<a href="http://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm" rel="nofollow">数据类型”，标准 ML 编程，作者：Robert Harper（2000 ）。

另一个例子是通过产生式规则在形式语法中定义表达式，例如以下用于带括号的整数算术表达式：

datatype int_exp = plus of int_term * int_term
                 | minus of int_term * int_term
and     int_term = times of int_factor * int_factor
                 | divide of int_factor * int_factor
                 | modulo of int_factor * int_factor
and   int_factor = int_const of int
                 | paren of int_exp;

来自“<a href="http://homepages.inf.ed.ac.uk/stg/NOTES/node41.html" rel="nofollow">定义数据类型”。

我在 Wikipedia 上更新了“<a href="https://en.wikipedia.org/wiki/Mutual_recursion" rel="nofollow">相互递归”以给出示例（包括标准 ML）。