什么是相互递归类型？

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

相互递归数据类型的标准基本例子是树和森林：一个森林树木的列表，而一棵树是价值和森林（r的价值oot和子女的子树）。在标准ML这可以被定义为，允许空树：

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

从“Data Types”，在标准ML，由罗伯特·哈珀编程（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; 

从“Defining datatypes”。

我已在维基百科更新“Mutual recursion”以提供示例（包括标准ML）。