<aside> 💡 Mutual reference is the phenomenon that occurs whenever >1 data types reference each other in their type comments. The data arising from each data type can be thought of as mutually recursive.

When encountering mutually recursive data, all the functions in the mutual reference cycle should be templated immediately.

The relationships between mutually recursive data can be mapped out via arbitrary-arity trees. When looking for a specific node/piece of data within a arbitrary-arity tree, a programming technique known as backtracking can be used to conduct a “brute-force” search. Backtracking is also commonly used to solve constraint satisfaction problems (CSPs) such as the n-Queens problem and the Knight’s Tour.

</aside>

Mutually Recursive Data

• Arbitrary-arity trees are data structures that are arbitrarily wide and deep.
  • Example: File systems
  • Family trees are also arbitrary-arity trees. Each person can have an arbitrary amount of siblings, ancestors, and descendants.

Arbitrary (data) doesn’t mean large, and it doesn’t mean random. It just means that before we start out, we don’t know how big (the data) will be.

• At times, you may encounter a program with multiple data definitions which reference each other (and are reliant on each other in some way). Such data definitions are known as mutually-referential data definitions.
  • The self-reference cycle allows each element to have an arbitrary number of sub-elements (i.e. arbitrarily wide)
  • The mutual reference cycle, on the other hand, allows each sub-element to have an arbitrary amount of their own sub-elements (i.e. arbitrarily deep).

Elements in arbitrary-arity trees are both mutually referential and self-referential.

“The way I (track mutual references is to first) draw all the arrows.

Then I label all the self-reference arrows.

Then I put my finger on an arrow, and I start following it around through the types. And if I ever come back to that same arrow, then all those arrows along the way were part of a mutual reference cycle.

And then any arrows that aren't part of a mutual reference cycle and aren't part of a self-reference cycle are just ordinary reference arrows.

In this case where there's just two types, it's easy. But sometimes you could have mutual reference through three or four or five or six or more types, and then it's a little harder to get the arrows right.”

• When you notice mutually-referential data definitions, take note of the mutual reference rule:

  In the case of mutually-referential data definitions, when you template one function in the mutual-reference cycle you should immediately template all the functions in the mutual-reference cycle.

• The type comments and interpretations of the mutually referential types should be written together.