species- Computational combinatorial species

Safe HaskellNone



An interpretation of species as ordinary generating functions, which count unlabeled structures.



unlabeled :: SpeciesAST -> [Integer]Source

Extract the coefficients of an ordinary generating function as a list of Integers. In particular, unlabeled s !! n is the number of unlabeled s-structures on an underlying set of size n (unlabeled s is guaranteed to be infinite). For example:

 > take 10 $ unlabeled octopi

gives the number of unlabeled octopi on 0, 1, 2, 3, ... 9 elements.

Actually, the above is something of a white lie, as you may have already realized by looking at the input type of unlabeled, which is SpeciesAST rather than the expected GF. The reason is that although products and sums of unlabeled species correspond to products and sums of ordinary generating functions, other operations such as composition and differentiation do not! In order to compute an ordinary generating function for a species defined in terms of composition and/or differentiation, we must compute the cycle index series for the species and then convert it to an ordinary generating function. So unlabeled actually works by first reifying the species to an AST and checking which operations are used in its definition, and then choosing to work with cycle index series or directly with (much faster) ordinary generating functions as appropriate.

unlabelled :: SpeciesAST -> [Integer]Source

A synonym for unlabeled, since both spellings are acceptable.