Module tree

Double trees: pasting diagrams in virtual double categories.

A double tree (nonstandard term) is the data structure for a pasting diagram in a virtual double category. To be more precise, a double tree is (up to isomorphism) a normal form for a general composition of cells in a VDC. That is, every sequence of composing cells and forming identity cells can be represented as a double tree, and, moreover, any two sequences equivalent under the associativity and unitality axioms of a VDC are represented by the same double tree.

Yet another way to say this is that double trees are the cells of free VDCs, generalizing how trees are the morphisms of free multicategories. Turning this around, we use our data structure for trees, specifically open trees, to implement double trees, the idea being that a double tree is an open tree whose types are proarrows and operations are cells, subject to additional typing constraints on the sources and targets.

The only hitch in this plan is that composition in a VDC includes the degenerate case of composing a cell with a zero-length path of cells, which is just a single arrow. To accomodate the degenerate case, the nodes in a double tree contain either cells or arrows. This complicates the code in a few places, since it is now possible for a nullary operation (cell) to have a child node, and it gives the data structure something of the spirit of augmented virtual double categories (Koudenburg 2020). We do not however implement pasting diagrams in augmented VDCs, which would introduce further complications.

Structs

DblTree

A double tree, or pasting diagram in a virtual double category.

Enums

DblNode

A node in a double tree.