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
- labeled :: EGF -> [Integer]
- labelled :: EGF -> [Integer]
- unlabeled :: SpeciesAST -> [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 SpeciesAST
- reify :: SpeciesAST -> SpeciesAST
- reflect :: Species s => SpeciesAST -> s
- data TSpeciesAST s
- data ESpeciesAST
- wrap :: Typeable1 s => TSpeciesAST s -> ESpeciesAST
- unwrap :: Typeable1 s => ESpeciesAST -> TSpeciesAST s
- erase :: ESpeciesAST -> SpeciesAST
- erase' :: TSpeciesAST f -> SpeciesAST
- annotate :: SpeciesAST -> ESpeciesAST
- simplify :: SpeciesAST -> SpeciesAST
- sumOfProducts :: SpeciesAST -> [[SpeciesAST]]
- class (Typeable f, Show f, Typeable1 (Interp f (Mu f))) => ASTFunctor f where
- apply :: Typeable1 g => f -> TSpeciesAST g -> TSpeciesAST (Interp f g)

- type family Interp f self :: * -> *
- newtonRaphsonRec :: (ASTFunctor f, Species s) => f -> Integer -> Maybe s
- newtonRaphson :: Species s => s -> Integer -> s
- deriveDefaultSpecies :: Name -> Q [Dec]
- 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`

,
`><`

, `@@`

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

.

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

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

can be applied directly to an expression
of the species DSL. In particular,

is the
number of labeled `labeled`

s `!!`

n`s`

-structures on an underlying set of size `n`

(note that

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

s

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

gives the number of labeled octopi on 0, 1, 2, 3, ... 9 labels.

labelled :: EGF -> [Integer]Source

A synonym for `labeled`

, since both spellings are acceptable and
it's annoying to have to remember which is correct.

unlabeled :: SpeciesAST -> [Integer]Source

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

is the
number of unlabeled `unlabeled`

s `!!`

n`s`

-structures on an underlying set of size
`n`

(`unlabeled s`

is guaranteed to be infinite). For example:

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

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.

# Enumerating species structures

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 at the `ghci`

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

Labeled 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. This is slightly more efficient than
`enumerate`

for lists of labels which are known to be distinct,
since it doesn't have to waste time checking for
duplicates. (However, it probably doesn't really make much
difference, since the time to do the actual enumeration will
usually dwarf the time to process the list of labels anyway.)

For example:

> enumerateL ballots [1,2,3] :: [Comp [] Set Int] [[{1,2,3}],[{2,3},{1}],[{1},{2,3}],[{2},{1,3}],[{1,3},{2}],[{3},{1,2}] ,[{1,2},{3}],[{3},{2},{1}],[{3},{1},{2}],[{2},{3},{1}],[{2},{1},{3}] ,[{1},{3},{2}],[{1},{2},{3}]]

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

Unlabeled enumeration: given a species expression and an integer
indicating the number of labels to use, compute the list of all
unlabeled 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 ())

For example:

> enumerateU octopi 4 :: [Comp Cycle [] ()] [<[(),(),(),()]>,<[(),()],[(),()]>,<[(),(),()],[()]> ,<[(),()],[()],[()]>,<[()],[()],[()],[()]>]

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 labeled structures, using [1..] as the labels.

For example:

> take 10 $ enumerateAll ballots :: [Comp [] Set Int] [[],[{1}],[{1,2}],[{2},{1}],[{1},{2}],[{1,2,3}],[{2,3},{1}] ,[{1},{2,3}],[{2},{1,3}],[{1,3},{2}]]

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

Lazily enumerate all unlabeled structures.

For example:

> take 10 $ enumerateAllU octopi :: [Comp Cycle [] ()] [<[()]>,<[(),()]>,<[()],[()]>,<[(),(),()]>,<[(),()],[()]> ,<[()],[()],[()]>,<[(),(),(),()]>,<[(),()],[(),()]> ,<[(),(),()],[()]>,<[(),()],[()],[()]>]

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

Species expressions can be reified into one of several AST types.

data SpeciesAST Source

A basic, untyped AST type for species expressions, for easily
doing things like analysis, simplification, deriving isomorphisms,
and so on. Converting between `SpeciesAST`

and the typed variant
`ESpeciesAST`

can be done with `annotate`

and `erase`

.

Eq SpeciesAST | Species expressions can be compared for Note, however, that species containing an |

Ord SpeciesAST | An (arbitrary) |

Show SpeciesAST | Display species expressions in a nice human-readable form. Note that we commit the unforgivable sin of omitting a corresponding Read instance. This will hopefully be remedied in a future version. |

C SpeciesAST | Species expressions are differentiable. |

C SpeciesAST | Species expressions form a ring. Well, sort of. Of course the ring laws actually only hold up to isomorphism of species, not up to structural equality. |

C SpeciesAST | Species expressions are additive. |

Species SpeciesAST | Species expressions are an instance of the |

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.

data TSpeciesAST s Source

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.

Show (TSpeciesAST s) |

data ESpeciesAST Source

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

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

.

wrap :: Typeable1 s => TSpeciesAST s -> ESpeciesASTSource

Construct an `ESpeciesAST`

from a `TSpeciesAST`

by adding an
appropriate interval annotation and hiding the type.

unwrap :: Typeable1 s => ESpeciesAST -> TSpeciesAST sSource

Unwrap an existential wrapper to get out a typed AST. You can get out any type you like as long as it is the right one.

CAUTION: Don't try this at home!

erase :: ESpeciesAST -> SpeciesASTSource

Erase the type and interval information from an existentially wrapped species AST.

erase' :: TSpeciesAST f -> SpeciesASTSource

Erase the type and interval information from a typed species AST.

annotate :: SpeciesAST -> ESpeciesASTSource

Reconstruct the type and interval annotations on a species AST.

# Species simplification

simplify :: SpeciesAST -> SpeciesASTSource

Given a species expression `s`

, return a species expression
in normal form which represents a species isomorphic to `s`

.

sumOfProducts :: SpeciesAST -> [[SpeciesAST]]Source

Simplify a species and decompose it into a sum of products.

# Recursive species

Tools for dealing with recursive species.

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

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`

.

newtonRaphsonRec :: (ASTFunctor f, Species s) => f -> Integer -> Maybe sSource

tries to compute the recursive species
represented by the code `newtonRaphsonRec`

f k`f`

up to order at least `k`

, using
Newton-Raphson iteration. Returns `Nothing`

if `f`

cannot be
written in the form `f = X*R(f)`

for some species `R`

.

newtonRaphson :: Species s => s -> Integer -> sSource

Given a species `r`

and a desired accuracy `k`

,

computes a species which has contact at least `newtonRaphson`

r k`k`

with the
species `t = x `

.
`*`

(r ``o`

` t)

# Template Haskell

deriveDefaultSpecies :: Name -> Q [Dec]Source

Generate default species declarations for the given user-defined data type. To use it:

{-# LANGUAGE TemplateHaskell, TypeFamilies, DeriveDataTypeable, FlexibleInstances, UndecidableInstances #-} data MyType = ... $(deriveDefaultSpecies ''MyType)

Yes, you really do need all those extensions. And don't panic
about the `UndecidableInstances`

; the instances generated
actually are decidable, but GHC just can't tell.

This is what you get:

- An
`Enumerable`

instance for`MyType`

(and various other supporting things like a code and an`ASTFunctor`

instance if your data type is recursive) - A declaration of
`myType :: Species s => s`

(the same name as the type constructor but with the first letter lowercased)

You can then use `myType`

in any species expression, or as input
to any function expecting a species. For example, to count your
data type's distinct shapes, you can do

take 10 . unlabeled $ myType

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