Trees
Trees are fundamental data structures in programming, where they are used to represent programs, mathematical expressions, and other nested data. Despite their widespread use and apparent simplicity, it seems difficult to give a mathematical description of trees that is both elegant and concrete (nCat Cafe ).
Trees as free multicategories
Planar trees over a signature (allowing input edges) can be succintly defined as the free multicategory generated by a multigraph. Extracting a concrete description of such trees is more involved. See also Todd Trimble’s writings on the nLab about the free multicategory and the free cartesian category on a signature .
- Batanin, 1998: Monoidal globular categories as a natural environment for the
theory of weak n-categories (doi)
- Example 3.8 formulates planar trees categorically in more detail than usual
- See also: Street, 1998: The role of Michael Batanin’s monoidal globular categories
- Hermida, 2000: Representable multicategories (doi), Section 5: Free
multicategories and trees
- Refers to Batanin for formal definition of tree; however, that definition does not seem to distinguish between input edges and nullary nodes
- Weber, 2007: Familial 2-functors and parametric right adjoints (pdf)
- Example 2.14 gives both an intuitive and a formal description of trees suitable for symmetric multicategories
- Garner & Hirschowitz, 2018: Shapely monads and analytic functors (doi, arxiv)
- Definition 2.7 defines a polycategorical tree to be a polygraph that is acyclic and satisfies other conditions
- Kock, 2011: Polynomial functors and trees (doi, arxiv)
- Formalizes trees suitable for operad theory as polynomial functors subject to special conditions