Что такое взаимно-рекурсивный тип?

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 и поддеревья его детей). В Standard ML это можно определить следующим образом, позволяя пустые деревья:

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

от «Data Types» Программирование в Standard 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).