types - 相互再帰型とは何ですか？

Question

MLの場合、再帰データ型の例は次のとおりです。

datatype llist = Nil | Node of int * llist

MLでの相互再帰データ型とは何ですか？その例は何ですか？

Answer 1

そのような例の 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 年) より）。

もう 1 つの例は、次のように整数の括弧で囲まれた算術式のように、生成規則を介して正式な文法で式を定義することです。

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">データ型の定義」から。

ウィキペディアの「<a href="https://en.wikipedia.org/wiki/Mutual_recursion" rel="nofollow">相互再帰」を更新して、例を示しました (標準 ML を含む)。