Editing Mutual recursion (section)

===Datatypes===
{{further|Recursive data type}}
The most important basic example of a datatype that can be defined by mutual recursion is a [[tree (data structure)|tree]], which can be defined mutually recursively in terms of a forest (a list of trees). Symbolically:
 f: <nowiki>[t[1], ..., t[k]]</nowiki>
 t: v f
A forest ''f'' consists of a list of trees, while a tree ''t'' consists of a pair of a value ''v'' and a forest ''f'' (its children). This definition is elegant and easy to work with abstractly (such as when proving theorems about properties of trees), as it expresses a tree in simple terms: a list of one type, and a pair of two types. Further, it matches many algorithms on trees, which consist of doing one thing with the value, and another thing with the children.

This mutually recursive definition can be converted to a singly recursive definition by [[Inline expansion|inlining]] the definition of a forest:
 t: v <nowiki>[t[1], ..., t[k]]</nowiki>
A tree ''t'' consists of a pair of a value ''v'' and a list of trees (its children). This definition is more compact, but somewhat messier: a tree consists of a pair of one type and a list of another, which require disentangling to prove results about.

In [[Standard ML]], the tree and forest datatypes can be mutually recursively defined as follows, allowing empty trees:{{sfn|Harper|2000|loc="[https://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm Date Types]"}}
<syntaxhighlight lang="sml">
datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest
</syntaxhighlight>