what is a mutually recursive type?

Question

If in ML, an example of a recursive datatype is:

datatype llist = Nil | Node of int * llist

What is a mutually recursive datatype and whats an example of it, in ML?

Hereunder

Answer 1

One such example could be these stupid datatypes.

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

They make no sense, but they show that it is possible to use the and keyword (just as with functions) to reference something "ahead" which is normally not possible

They are mutually (as they both...) recursive (...reference each other)

Galloot

Answer 2

The standard basic example of mutually recursive data types is a tree and a forest: a forest is a list of trees, while a tree is a value and a forest (the value of the root and the subtrees of its children). In Standard ML this can be defined as follows, allowing empty trees:

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

from “Data Types”, Programming in Standard ML, by Robert Harper (2000).

Another example is defining expressions in a formal grammar via production rules, such as the following for parenthesized arithmetic expressions of integers:

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;

from “Defining datatypes”.

I’ve updated “Mutual recursion” at Wikipedia to give examples (including Standard ML).

Howl