|The Species type class, which defines a small DSL for describing
combinatorial species. Other modules in this library provide
specific instances which allow computing various properties of
|The Species type class
The Species type class. Note that the Differential constraint
requires s to be a differentiable ring, which means that every
instance must also implement instances for Algebra.Additive
(the species 0 and species addition, i.e. disjoint sum),
Algebra.Ring (the species 1 and species multiplication,
i.e. partitional product), and Algebra.Differential (species
differentiation, i.e. adjoining a distinguished element).
Minimal complete definition: singleton, set, cycle, o,
cartesian, fcomp, ofSize.
Note that the o operation can be used infix to suggest common
notation for composition, and also to be read as an abbreviation
for "of", as in "top o' the mornin'": set `o` nonEmpty
In this version of the library, Species has four instances:
EGF (exponential generating functions, for counting labelled
structures), GF (ordinary generating function, for counting
unlabelled structures), CycleIndex (cycle index series, a
generalization of both EGF and GF), and SpeciesAST (reified
|The species X of singletons. X puts a singleton structure on an
underlying set of size 1, and no structures on any other
|The species E of sets. E puts a singleton structure on any
|The species C of cyclical orderings (cycles/rings).
|The species L of linear orderings (lists): since lists are
isomorphic to cycles with a hole, we may take L = C' as the
default implementation; list is included in the Species class
so it can be special-cased for generation.
|The species p of subsets is given by p = E * E. subset has a
default implementation of set * set, but is included in the
Species class so it can be overridden when generating
structures: since subset is defined as set * set, the
generation code by default generates a pair of the subset and
its complement, but normally when thinking about subsets we
only want to see the elements in the subset. To explicitly
generate subset/complement pairs, you can use set * set
|Subsets of size exactly k, p[k] = E_k * E. Included with a
default definition in the Species class for the same reason
|Structures of the species e of elements are just elements of
the underlying set: e = X * E. Included with default
definition in Species class for the same reason as subset
|Partitional composition. To form all (F o G)-structures on the
underlying set U, first form all set partitions of U; for each
partition p, put an F-structure on the classes of p, and a
separate G-structure on the elements in each class.
|cartesian :: s -> s -> s||Source|
|Cartisian product of two species. An (F x G)-structure
consists of an F structure superimposed on a G structure over
the same underlying set.
|Functor composition of two species. An (F @@ G)-structure
consists of an F-structure on the set of all G-structures.
|Only put a structure on underlying sets whose size satisfies
|Only put a structure on underlying sets of the given size. A
default implementation of ofSize (==k) is provided, but this
method is included in the Species class as a special case
since it can be more efficient: we get to turn infinite lists
of coefficients into finite ones.
|Don't put a structure on the empty set. The default definition
uses ofSize; included in the Species class so it can be
overriden in special cases (such as when reifying species
|A convenient synonym for differentiation. F'-structures look
like F-structures on a set formed by adjoining a distinguished
"hole" element to the underlying set.
|A synonym for o (partitional composition).
|A synonym for cartesian product.
|A synonym for functor composition.
|A synonym for singleton.
|Some derived operations on species.
|Combinatorially, the operation of pointing picks out a
distinguished element from an underlying set. It is equivalent
to the operator x d/dx.
|Some species that can be defined in terms of the primitive species
|An octopus is a cyclic arrangement of lists, so called because
the lists look like "tentacles" attached to the cyclic
"body": Oct = C o E+ .
|The species of set partitions is just the composition E o E+,
that is, sets of nonempty sets.
|A permutation is a set of disjoint cycles: S = E o C.
|The species Bal of ballots consists of linear orderings of
nonempty sets: Bal = L o E+.
|Simple graphs (undirected, without loops). A simple graph is a
subset of the set of all size-two subsets of the vertices: G = p
|A directed graph (with loops) is a subset of all pairs drawn
(without replacement) from the set of vertices: D = p @@ (e ><
e). It can also be thought of as the species of binary relations.
|Produced by Haddock version 2.6.0|