Combinatorial species
Combinatorial species are presheaves (or equivalently copresheaves) on the category of finite sets and bijections. Species were invented by Joyal as a categorification of generating functions in enumerative combinatorics.
Species
Books
- Bergeron, Labelle, Leroux, 1998: Combinatorial species and tree-like structures (doi)
- Bergeron, Labelle, Leroux, 2008: Introduction to the theory of species of structures (pdf)
- Aguiar & Mahajan, 2010: Monoidal functors, species and Hopf algebras (doi, pdf)
Applications to computer science
There are connections between combinatorial species, algebraic data types, and polynomial functors.
Generalized species
Combinatorial species can be generalized in many directions. See (Yorgey, 2014, Chapter 5: Species variants) for a survey up to that date.
- Fiore, Gambino, Hyland, Winskel, 2007: The cartesian closed bicategory of
generalised species of structures (doi)
- Two generalizations: indexing by families in a category \(A\) (with bijective reindexings) and taking values in presheaves over a category \(B\)
- Putting \(A = B = 1\), the terminal category, recovers standard species
- Fiore, Galal, Paquet, 2024: Stabilized profunctors and stable species of
structures (doi, arxiv)
- Figure 1 compares “extensional” and “intensional” presentations for polynomial functors, analytic functors, and related notions
Multi-sorted species
A \(k\)-sorted species is a presheaf on the \(k\)th power of the category of finite sets and bijections.
- Bergeron et al, 2008, Section 3.2: Extension to the multisort context
- Yorgey, 2014, PhD thesis, Section 5.4: Multisort species
Restriction species
A restriction species, as defined by William Schmitt, is a presheaf on the category of finite sets and injections. Because every injection factors as a bijection followed by an inclusion, a restriction species can be seen as an ordinary species equipped with a functorial family of restriction maps.