Math.Combinatorics.Species.Class

The Species type class, which defines a small DSL for describing combinatorial species. Other modules in this library provide specific instances which allow computing various properties of combinatorial species.

The Species type class

class C s => Species s where

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

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.

Methods

singleton :: s

The species X of singletons

set :: s

The species E of sets

cycle :: s

The species C of cyclical orderings (cycles/rings)

o :: s -> s -> s

Partitional composition

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

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

ofSizeExactly :: s -> Integer -> s

Only put a structure on underlying sets of the given size. We include this as a special case, instead of just using ofSize (==k), since it can be more efficient: we get to turn infinite lists of coefficients into finite ones.

(.:) :: s -> s -> s

s1 .: s2 is the species which puts an s1 structure on the empty set and an s2 structure on anything else. Useful for getting recursively defined species off the ground.

Instances

Species CycleIndex

Species GF

Species EGF

Species SpeciesAlg

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

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.

madeOf :: Species s => s -> s -> s

A synonym for o (partitional composition).

x :: Species s => s

A synonym for singleton.

e :: Species s => s

A synonym for set.

sets :: Species s => s

cycles :: Species s => s

Derived operations

Some derived operations on species.

pointed :: Species s => s -> s

Combinatorially, the operation of pointing picks out a distinguished element from an underlying set. It is equivalent to the operator x d/dx.

nonEmpty :: Species s => s -> s

Don't put a structure on the empty set.

Derived species

Some species that can be defined in terms of the primitive species operations.

list :: Species s => s

The species L of linear orderings (lists): since lists are isomorphic to cycles with a hole, we may take L = C'.

lists :: Species s => s

A convenient synonym for list.

element :: Species s => s

Structures of the species eps of elements are just elements of the underlying set: eps = X * E.

elements :: Species s => s

octopus :: Species s => s

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

octopi :: Species s => s

partition :: Species s => s

The species of set partitions is just the composition E o E+, that is, sets of nonempty sets.

partitions :: Species s => s

permutation :: Species s => s

A permutation is a set of disjoint cycles: S = E o C.

permutations :: Species s => s

subset :: Species s => s

The species p of subsets is given by p = E * E.

subsets :: Species s => s

ballot :: Species s => s

The species Bal of ballots consists of linear orderings of nonempty sets: Bal = L o E+.

ballots :: Species s => s

ksubset :: Species s => Integer -> s

Subsets of size exactly k, p[k] = E_k * E.

ksubsets :: Species s => Integer -> s