| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Description | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Synopsis | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The combinatorial species DSL | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The combinatorial species DSL consists of the Species type class,
which defines some primitive species and species operations.
Expressions of type Species s => s can then be interpreted at
various instance types in order to compute with species in various
ways.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Convenience methods | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Some synonyms are provided for convenience. In particular,
gramatically it can often be convenient to have both the singular
and plural versions of species, for example, set `o` nonEmpty
sets.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Derived operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 size-two 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. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Computing with species | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Extract the coefficients of an exponential generating function as
a list of Integers. Since > 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, > 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generating species structures | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> 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 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 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 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

s.
In particular, if structureType s prints "T", then you can
safely use generateTyped by writing
generateTyped s ls :: [T L] where | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Types used for generation | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Many of these functors are already defined elsewhere, in other packages; but to avoid a plethora of imports, inconsistent naming/instance schemes, etc., we just redefine them here. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Species AST | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Species can be converted to and from SpeciesAST via the functions
reify and reflect.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 . C'+ > reify (ksubset 3) E3 * E | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Reflect an AST back into any instance of the Species class.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Produced by Haddock version 2.6.0 |