
Math.Combinatorics.Species.Class 




Description 
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
combinatorial species.


Synopsis 




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
sets.
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
species expressions).
  Methods   The species X of singletons. X puts a singleton structure on an
underlying set of size 1, and no structures on any other
underlying sets.
   The species E of sets. E puts a singleton structure on any
underlying set.
   The species C of cyclical orderings (cycles/rings).
   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
directly.
   Subsets of size exactly k, p[k] = E_k * E. Included with a
default definition in the Species class for the same reason
as subset.
   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
and ksubset.
   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 Fstructure on the classes of p, and a
separate Gstructure 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 Fstructure on the set of all Gstructures.
   Only put a structure on underlying sets whose size satisfies
the predicate.
   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
expressions).

  Instances  


Convenience methods



A convenient synonym for differentiation. F'structures look
like Fstructures 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.












Derived operations


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.


Derived species


Some species that can be defined in terms of the primitive species
operations.



The species L of linear orderings (lists): since lists are
isomorphic to cycles with a hole, we may take L = C'.





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 sizetwo subsets of the vertices: G = p
@@ p_2.





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 