A DSL for describing and computing with combinatorial species. This module re-exports the most generally useful functionality; for more specialized functionality (for example, computing directly with cycle index series), see the various sub-modules.

Note that this library makes extensive use of the numeric-prelude library; to use it you will want to use -XNoImplicitPrelude, and import NumericPrelude and PreludeBase.

For a friendly introduction to combinatorial species in general and this library in particular, see my series of blog posts:

http://byorgey.wordpress.com/2009/07/24/introducing-math-combinatorics-species/

For a good reference (really, the only English-language reference!) on combinatorial species, see Bergeron, Labelle, and Leroux, "Combinatorial Species and Tree-Like Structures", Vol. 67 of the Encyclopedia of Mathematics and its Applications, Gian-Carlo Rota, ed., Cambridge University Press, 1998.

Extract the coefficients of an exponential generating function as a list of Integers. Since EGF is an instance of Species, the idea is that labelled can be applied directly to an expression of the Species DSL. In particular, labelled s !! n is the number of labelled s-structures on an underlying set of size n (note that labelled s is guaranteed to be an infinite list). For example:

 > take 10 $ labelled octopi
 [0,1,3,14,90,744,7560,91440,1285200,20603520]

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

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

 > take 10 $ unlabelled octopi
 [0,1,2,3,5,7,13,19,35,59]

gives the number of unlabelled 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 unlabelled, which is SpeciesAST rather than the expected GF. The reason is that although products and sums of unlabelled 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 unlabelled 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.

generate s ls generates a complete list of all s-structures over the underlying set of labels ls. For example:

 > generate octopi ([1,2,3] :: [Int])
 [<<*,1,2,3>>,<<*,1,3,2>>,<<*,2,1,3>>,<<*,2,3,1>>,<<*,3,1,2>>,<<*,3,2,1>>,
  <<*,1,2>,<*,3>>,<<*,2,1>,<*,3>>,<<*,1,3>,<*,2>>,<<*,3,1>,<*,2>>,<<*,1>,
  <*,2,3>>,<<*,1>,<*,3,2>>,<<*,1>,<*,2>,<*,3>>,<<*,1>,<*,3>,<*,2>>]

 > generate subsets "abc"
 [{'a','b','c'},{'a','b'},{'a','c'},{'a'},{'b','c'},{'b'},{'c'},{}]

 > generate simpleGraphs ([1,2,3] :: [Int])
 [{{1,2},{1,3},{2,3}},{{1,2},{1,3}},{{1,2},{2,3}},{{1,2}},{{1,3},{2,3}},
  {{1,3}},{{2,3}},{}]

There is one caveat: since the type of the generated structures is different for each species, it must be existentially quantified! The output of generate can always be Shown, but not much else.

However! All is not lost. It's possible, by the magic of Data.Typeable, to yank the type information (kicking and screaming) back into the open, so that you can then manipulate the generated structures to your heart's content. To see how, consult structureType and generateTyped.

generateTyped s ls generates a complete list of all s-structures over the underlying set of labels ls, where the type of the generated structures is known (structureType may be used to compute this type). For example:

 > structureType subsets
 "Set"
 > generateTyped subsets ([1,2,3] :: [Int]) :: [Set Int]
 [{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{}]
 > map (sum . getSet) $ it
 [6,3,4,1,5,2,3,0]

Although the output from generate appears the same, trying to compute the subset sums fails spectacularly if we use generate instead of generateTyped:

 > generate subsets ([1..3] :: [Int])
 [{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{}]
 > map (sum . getSet) $ it
 <interactive>:1:21:
     Couldn't match expected type `Set a'
            against inferred type `Math.Combinatorics.Species.Generate.Structure
                                     Int'
       Expected type: [Set a]
       Inferred type: [Math.Combinatorics.Species.Generate.Structure Int]
     In the second argument of `($)', namely `it'
     In the expression: map (sum . getSet) $ it

If we use the wrong type, we get a nice error message:

 > generateTyped octopi ([1..3] :: [Int]) :: [Set Int]
 *** Exception: structure type mismatch.
   Expected: Set Int
   Inferred: Comp Cycle (Comp Cycle Star) Int

structureType s returns a String representation of the functor type which represents the structure of the species s. In particular, if structureType s prints "T", then you can safely use generateTyped by writing

 generateTyped s ls :: [T L]

where ls :: [L].

Reify a species expression into an AST. Of course, this is just the identity function with a usefully restricted type. For example:

 > reify octopus
 C . L+
 > reify (ksubset 3)
 E3 * E