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.
- 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
The Species type class
The Species type class. Note that the
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
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.
E of sets. Puts a singleton structure on any
underlying label set.
C of cyclical orderings (cycles/rings).
L of linear orderings (lists). Since linear
orderings are isomorphic to cyclic orderings with a hole, we
as the default
linOrd is included in the
Species class so it
can be special-cased for enumeration.
p of subsets is given by
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
Structures of the species
e of elements are just elements of
the underlying set,
with a default definition in
Species class for the same
Partitional composition. To form all
(f `-structures on
the underlying label set U, first form all set partitions of U;
for each partition
p, put an
f-structure on the classes of
p, and a separate
g-structure on the elements in each
Cartisian product of two species. An
consists of an
f-structure superimposed on a
the same underlying set.
Functor composition of two species. An
consists of an
f-structure on the set of all
Only put a structure on underlying sets whose size satisfies the predicate.
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.
'rec f' is the least fixpoint of (the interpretation of) the
higher-order species constructor
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 expressions are an instance of the
A convenient synonym for differentiation.
-structures look like
f-structures on a set formed by adjoining
a distinguished "hole" element to the underlying set.
Some derived operations on species.
Some species that can be defined in terms of the primitive species operations.