So far, the definitions have assumed that all sub structures are distinct, and that arbitrarily traversing a structure can never bring us back to the same position. I shall extend the definition to allow for two situations where we can reach the same node from different routes. This does not extend to the most general case where any node can access any other node, such as in a graph, but it does allow us to have some additional structure.
Firstly, the idea of two directions being inverses of each other. The simplest instance of this would be a doubly linked list, where we have two possible directions next and prev . Another example would be a binary tree with an additional node parent .
Secondly, I will consider the situation where two directions can commute . Consider a simple mesh of nodes. If we describe the two directions as north and east , then we clearly reach the same point by travelling north , east that we reach by moving east and north . So if we want to include these structures in our data types then commutative directions will be needed. Obviously we can extend this to allow commutativity between any pairs of direction that we choose, although this might not create particularly useful structures, apart from the ones for the evaluation of recursive functions mentioned earlier. The mesh or `Diamond DAG' is, however another example, used in the solution of partial differential equations.
