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/
- http://byorgey.wordpress.com/2009/07/30/primitive-species-and-species-operations/
- http://byorgey.wordpress.com/2009/07/31/primitive-species-and-species-operations-part-ii/

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.

- class C s => Species s where
- oneHole :: Species s => s -> s
- x :: Species s => s
- sets :: Species s => s
- cycles :: Species s => s
- linOrds :: Species s => s
- subsets :: Species s => s
- ksubsets :: Species s => Integer -> s
- elements :: Species s => s
- pointed :: Species s => s -> s
- octopus :: Species s => s
- octopi :: Species s => s
- partition :: Species s => s
- partitions :: Species s => s
- permutation :: Species s => s
- permutations :: Species s => s
- ballot :: Species s => s
- ballots :: Species s => s
- simpleGraph :: Species s => s
- simpleGraphs :: Species s => s
- directedGraph :: Species s => s
- directedGraphs :: Species s => s
- labelled :: EGF -> [Integer]
- unlabelled :: SpeciesAST -> [Integer]
- class Typeable1 (StructTy f) => Enumerable f where
- structureType :: ESpeciesAST -> String
- enumerate :: (Enumerable f, Typeable a, Eq a) => SpeciesAST -> [a] -> [f a]
- enumerateL :: (Enumerable f, Typeable a) => SpeciesAST -> [a] -> [f a]
- enumerateU :: Enumerable f => SpeciesAST -> Int -> [f ()]
- enumerateM :: (Enumerable f, Typeable a) => SpeciesAST -> Multiset a -> [f a]
- enumerateAll :: Enumerable f => SpeciesAST -> [f Int]
- enumerateAllU :: Enumerable f => SpeciesAST -> [f ()]
- data Void a
- data Unit a = Unit
- newtype Id a = Id a
- newtype Const x a = Const x
- data Sum f g a
- data Prod f g a = Prod (f a) (g a)
- data Comp f g a = Comp {
- unComp :: f (g a)

- data Star a
- newtype Cycle a = Cycle {
- getCycle :: [a]

- newtype Set a = Set {
- getSet :: [a]

- data TSpeciesAST s where
- TZero :: TSpeciesAST Void
- TOne :: TSpeciesAST Unit
- TN :: Integer -> TSpeciesAST (Const Integer)
- TX :: TSpeciesAST Id
- TE :: TSpeciesAST Set
- TC :: TSpeciesAST Cycle
- TL :: TSpeciesAST []
- TSubset :: TSpeciesAST Set
- TKSubset :: Integer -> TSpeciesAST Set
- TElt :: TSpeciesAST Id
- :+:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Sum f g)
- :*:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Prod f g)
- :.:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Comp f g)
- :><:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Prod f g)
- :@:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Comp f g)
- TDer :: SizedSpeciesAST f -> TSpeciesAST (Comp f Star)
- TOfSize :: SizedSpeciesAST f -> (Integer -> Bool) -> TSpeciesAST f
- TOfSizeExactly :: SizedSpeciesAST f -> Integer -> TSpeciesAST f
- TNonEmpty :: SizedSpeciesAST f -> TSpeciesAST f
- TRec :: ASTFunctor f => f -> TSpeciesAST (Mu f)
- TOmega :: TSpeciesAST Void

- data ESpeciesAST where
- Wrap :: Typeable1 s => SizedSpeciesAST s -> ESpeciesAST

- reify :: SpeciesAST -> SpeciesAST
- reflect :: Species s => SpeciesAST -> s
- data Mu f a = Mu {}
- type family Interp f self :: * -> *
- class (Typeable f, Show f, Typeable1 (Interp f (Mu f))) => ASTFunctor f where
- apply :: Typeable1 g => f -> TSpeciesAST g -> TSpeciesAST (Interp f g)

- deriveSpecies :: Name -> SpeciesAST -> Q [Dec]

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

class C s => Species s whereSource

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

.

The species `X`

of singletons. Puts a singleton structure on an
underlying label set of size 1, and no structures on any other
underlying label sets. `x`

is also provided as a synonym.

The species `E`

of sets. Puts a singleton structure on *any*
underlying label set.

The species `C`

of cyclical orderings (cycles/rings).

The species `L`

of linear orderings (lists). Since linear
orderings are isomorphic to cyclic orderings with a hole, we
may take

as the default
implementation; `linOrd`

= `oneHole`

`cycle`

`linOrd`

is included in the `Species`

class so it
can be special-cased for enumeration.

The species `p`

of subsets is given by

. `subset`

= `set`

*
`set`

`subset`

is included in the `Species`

class so it can
be overridden when enumerating structures: by default the
enumeration code would generate 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
enumerate subset/complement pairs, you can use

directly.
`set`

* `set`

Subsets of size exactly k,

. Included with a default definition
in the `ksubset`

k = (`set`

``ofSizeExactly`

` k) * `set`

`Species`

class for the same reason as `subset`

.

Structures of the species `e`

of elements are just elements of
the underlying set,

. Included
with a default definition in `element`

= `singleton`

* `set`

`Species`

class for the same
reason as `subset`

and `ksubset`

.

Partitional composition. To form all `(f ``

-structures on
the underlying label set U, first form all set partitions of U;
for each partition `o`

` g)`p`

, put an `f`

-structure on the classes of
`p`

, and a separate `g`

-structure on the elements in each
class.

Cartisian product of two species. An `(f `

-structure
consists of an `><`

g)`f`

-structure superimposed on a `g`

-structure over
the same underlying set.

Functor composition of two species. An `(f `

-structure
consists of an `@@`

g)`f`

-structure on the set of all `g`

-structures.

ofSize :: s -> (Integer -> Bool) -> sSource

Only put a structure on underlying sets whose size satisfies the predicate.

ofSizeExactly :: s -> Integer -> sSource

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

rec :: ASTFunctor f => f -> sSource

'rec f' is the least fixpoint of (the interpretation of) the
higher-order species constructor `f`

.

Omega is the pseudo-species which only puts a structure on infinite label sets. Of course this is not really a species, but it is sometimes a convenient fiction to use Omega to stand in for recursive occurrences of a species.

Species CycleIndex | An interpretation of species expressions as cycle index series.
For the definition of the |

Species GF | |

Species EGF | |

Species ESpeciesAST | |

Species SpeciesAST | Species expressions are an instance of the |

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

.

oneHole :: Species s => s -> sSource

A convenient synonym for differentiation.

-structures look like `oneHole`

f`f`

-structures on a set formed by adjoining
a distinguished "hole" element to the underlying set.

## Derived operations

## Derived species

partitions :: Species s => sSource

permutation :: Species s => sSource

A permutation is a set of disjoint cycles:

.
`permutation`

= `set`

``o`

` `cycles`

permutations :: Species s => sSource

simpleGraph :: Species s => sSource

Simple graphs (undirected, without loops). A simple graph is a
subset of the set of all size-two subsets of the vertices:

.
`simpleGraph`

= `subset`

`@@`

(`ksubset`

2)

simpleGraphs :: Species s => sSource

directedGraph :: Species s => sSource

directedGraphs :: Species s => sSource

# Counting species structures

XXX

labelled :: EGF -> [Integer]Source

Extract the coefficients of an exponential generating function as
a list of `Integer`

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

is the
number of labelled `labelled`

s `!!`

n`s`

-structures on an underlying set of size `n`

(note that

is guaranteed to be an infinite list).
For example:
`labelled`

s

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

unlabelled :: SpeciesAST -> [Integer]Source

Extract the coefficients of an ordinary generating function as a
list of Integers. In particular,

is the
number of unlabelled `unlabelled`

s `!!`

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

# Enumerating species structures

XXX

class Typeable1 (StructTy f) => Enumerable f whereSource

The `Enumerable`

class allows you to enumerate structures of any
type, by declaring an instance of `Enumerable`

. The `Enumerable`

instance requires you to declare a standard structure type (see
Math.Combinatorics.Species.Structures) associated with your
type, and a mapping `iso`

from the standard type to your custom
one. Instances are provided for all the standard structure types
so you can enumerate species without having to provide your own
custom data type as the target of the enumeration if you don't
want to.

You should only rarely have to explicitly make an instance of
`Enumerable`

yourself; Template Haskell code to derive instances
for you is provided in Math.Combinatorics.Species.TH.

type StructTy f :: * -> *Source

The standard structure type (see
Math.Combinatorics.Species.Structures) that will map into `f`

.

Enumerable [] | |

Enumerable Maybe | |

Enumerable Star | |

Enumerable Set | |

Enumerable Cycle | |

Enumerable Id | |

Enumerable Unit | |

Enumerable Void | |

Typeable f => Enumerable (Mu f) | |

Typeable a => Enumerable (Const a) | |

(Enumerable f, Functor f, Enumerable g) => Enumerable (Comp f g) | |

(Enumerable f, Enumerable g) => Enumerable (Prod f g) | |

(Enumerable f, Enumerable g) => Enumerable (Sum f g) |

structureType :: ESpeciesAST -> StringSource

returns a String representation of the
functor type which represents the structure of the species `structureType`

s`s`

.
In particular, if `structureType s`

prints `"T"`

, then you can
safely use `enumerate`

and friends by writing

enumerate s ls :: [T a]

where `ls :: [a]`

.

For example,

> structureType octopus "Comp Cycle []" > enumerate octopus [1,2,3] :: [Comp Cycle [] Int] [<[3,2,1]>,<[3,1,2]>,<[2,3,1]>,<[2,1,3]>,<[1,3,2]> ,<[1,2,3]>,<[1],[3,2]>,<[1],[2,3]>,<[3,1],[2]> ,<[1,3],[2]>,<[2,1],[3]>,<[1,2],[3]>,<[2],[1],[3]> ,<[1],[2],[3]>]

Note, however, that providing a type annotation on `enumerate`

in
this way is usually only necessary at the `ghci`

prompt; when used
in the context of a larger program the type of a call to
`enumerate`

can often be inferred.

enumerate :: (Enumerable f, Typeable a, Eq a) => SpeciesAST -> [a] -> [f a]Source

`enumerate s ls`

computes a complete list of distinct
`s`

-structures over the underlying multiset of labels `ls`

. For
example:

> enumerate octopi [1,2,3] :: [Comp Cycle [] Int] [<[3,2,1]>,<[3,1,2]>,<[2,3,1]>,<[2,1,3]>,<[1,3,2]>,<[1,2,3]>, <[1],[3,2]>,<[1],[2,3]>,<[3,1],[2]>,<[1,3],[2]>,<[2,1],[3]>, <[1,2],[3]>,<[2],[1],[3]>,<[1],[2],[3]>] > enumerate octopi [1,1,2] :: [Comp Cycle [] Int] [<[2,1,1]>,<[1,2,1]>,<[1,1,2]>,<[2,1],[1]>,<[1,2],[1]>, <[1,1],[2]>,<[1],[1],[2]>] > enumerate subsets "abc" :: [Set Int] [{'a','b','c'},{'a','b'},{'a','c'},{'a'},{'b','c'},{'b'},{'c'},{}] > enumerate simpleGraphs [1,2,3] :: [Comp Set Set 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, they must be cast (using the magic
of Data.Typeable) out of an existential wrapper; this is why
type annotations are required in all the examples above. Of
course, if a call to `enumerate`

is used in the context of some
larger program, a type annotation will probably not be needed,
due to the magic of type inference.

For help in knowing what type annotation you can give when
enumerating the structures of a particular species, see the
`structureType`

function. To be able to use your own custom data
type in an enumeration, just make your data type an instance of
the `Enumerable`

type class; this can be done for you
automatically by Math.Combinatorics.Species.TH.

If an invalid type annotation is given, `enumerate`

will call
`error`

with a helpful error message. This should not be much of
an issue in practice, since usually `enumerate`

will be used at a
specific type; it's hard to imagine a usage of `enumerate`

which
will sometimes work and sometimes fail. However, those who like
their functions total can use `extractStructure`

to make a
version of `enumerate`

(or the other variants) with a return type
of `[`

(which will return an annoying ton of
duplicate error messages) or `Either`

`String`

(f a)]

(which has the
unfortunate property of being much less lazy than the current
versions, since it must compute the entire list before deciding
whether to return `Either`

`String`

[f a]

or `Left`

).
`Right`

For slight variants on `enumerate`

, see `enumerateL`

,
`enumerateU`

, and `enumerateM`

.

enumerateL :: (Enumerable f, Typeable a) => SpeciesAST -> [a] -> [f a]Source

Labelled enumeration: given a species expression and a list of
labels (which are assumed to be distinct), compute the list of
all structures built from the given labels. If the type given
for the enumeration does not match the species expression (via an
`Enumerable`

instance), call `error`

with an error message
explaining the mismatch.

enumerateU :: Enumerable f => SpeciesAST -> Int -> [f ()]Source

Unlabelled enumeration: given a species expression and an integer
indicating the number of labels to use, compute the list of all
unlabelled structures of the given size. If the type given for
the enumeration does not match the species expression, call
`error`

with an error message explaining the mismatch.

Note that

is equivalent to `enumerateU`

s n

.
`enumerate`

s
(replicate n ())

enumerateM :: (Enumerable f, Typeable a) => SpeciesAST -> Multiset a -> [f a]Source

General enumeration: given a species expression and a multiset of
labels, compute the list of all distinct structures built from
the given labels. If the type given for the enumeration does not
match the species expression, call `error`

with a message
explaining the mismatch.

enumerateAll :: Enumerable f => SpeciesAST -> [f Int]Source

Lazily enumerate all labelled structures, using [1..] as the labels.

enumerateAllU :: Enumerable f => SpeciesAST -> [f ()]Source

Lazily enumerate all unlabelled structures.

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

The (constantly) void functor.

The (constantly) unit functor.

The identity functor.

Id a |

The constant functor.

Const x |

Functor coproduct.

Functor product.

Prod (f a) (g a) |

Functor composition.

Cycle structure. A value of type

is implemented as
`Cycle`

a`[a]`

, but thought of as a directed cycle.

Set structure. A value of type

is implemented as `Set`

a`[a]`

,
but thought of as an unordered set.

# Species AST

XXX

data TSpeciesAST s whereSource

A variant of `SpeciesAST`

with a phantom type parameter which
also reflects the structure, so we can write
quasi-dependently-typed functions over species, in particular for
species enumeration.

Of course, the non-uniform type parameter means that
`TSpeciesAST`

cannot be an instance of the `Species`

class; for
that purpose the existential wrapper `ESpeciesAST`

is provided.

`TSpeciesAST`

is defined via mutual recursion with
`SizedSpeciesAST`

, which pairs a `TSpeciesAST`

with an interval
annotation indicating (a conservative approximation of) the label
set sizes for which the species actually yields any structures;
this information makes enumeration faster and also prevents it
from getting stuck in infinite recursion in some cases. A value
of `SizedSpeciesAST`

is thus an annotated species expression tree
with interval annotations at every node.

TZero :: TSpeciesAST Void | |

TOne :: TSpeciesAST Unit | |

TN :: Integer -> TSpeciesAST (Const Integer) | |

TX :: TSpeciesAST Id | |

TE :: TSpeciesAST Set | |

TC :: TSpeciesAST Cycle | |

TL :: TSpeciesAST [] | |

TSubset :: TSpeciesAST Set | |

TKSubset :: Integer -> TSpeciesAST Set | |

TElt :: TSpeciesAST Id | |

:+:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Sum f g) | |

:*:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Prod f g) | |

:.:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Comp f g) | |

:><:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Prod f g) | |

:@:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (Comp f g) | |

TDer :: SizedSpeciesAST f -> TSpeciesAST (Comp f Star) | |

TOfSize :: SizedSpeciesAST f -> (Integer -> Bool) -> TSpeciesAST f | |

TOfSizeExactly :: SizedSpeciesAST f -> Integer -> TSpeciesAST f | |

TNonEmpty :: SizedSpeciesAST f -> TSpeciesAST f | |

TRec :: ASTFunctor f => f -> TSpeciesAST (Mu f) | |

TOmega :: TSpeciesAST Void |

Show (TSpeciesAST s) |

data ESpeciesAST whereSource

An existential wrapper to hide the phantom type parameter to
`SizedSpeciesAST`

, so we can make it an instance of `Species`

.

Wrap :: Typeable1 s => SizedSpeciesAST s -> ESpeciesAST |

reify :: SpeciesAST -> SpeciesASTSource

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

> reify octopus C . TL+ > reify (ksubset 3) E3 * TE

reflect :: Species s => SpeciesAST -> sSource

Reflect an AST back into any instance of the `Species`

class.

# Recursive species

XXX

Higher-order fixpoint.

is morally isomorphic to `Mu`

f a```
f
(
```

, except that we actually need a level of indirection.
In fact `Mu`

f) a

is isomorphic to `Mu`

f a

; `Interp`

f (`Mu`

f) a`f`

is a code which is interpreted by the `Interp`

type function.

Typeable2 Mu | |

Typeable f => Enumerable (Mu f) |

type family Interp f self :: * -> *Source

Interpretation type function for codes for higher-order type
constructors, used as arguments to the higher-order fixpoint `Mu`

.

class (Typeable f, Show f, Typeable1 (Interp f (Mu f))) => ASTFunctor f whereSource

`ASTFunctor`

is a type class for codes which can be interpreted
(via the `Interp`

type family) as higher-order functors over
species expressions. The `apply`

method allows such codes to be
applied to a species AST. The indirection is needed to implement
recursive species.

apply :: Typeable1 g => f -> TSpeciesAST g -> TSpeciesAST (Interp f g)Source

# Template Haskell

deriveSpecies :: Name -> SpeciesAST -> Q [Dec]Source

Like `deriveDefaultSpecies`

, except that you specify the species
expression that your data type should be isomorphic to. Note: this
is currently experimental (read: bug-ridden).