什麼是相互遞歸類型？

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）。