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
- madeOf :: Species s => s -> s -> s
- x :: Species s => s
- e :: Species s => s
- sets :: Species s => s
- cycles :: Species s => s
- pointed :: Species s => s -> s
- nonEmpty :: Species s => s -> s
- list :: Species s => s
- lists :: Species s => s
- element :: Species s => s
- elements :: Species 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
- subset :: Species s => s
- subsets :: Species s => s
- ballot :: Species s => s
- ballots :: Species s => s
- ksubset :: Species s => Integer -> s
- ksubsets :: Species s => Integer -> 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
The species X of singletons
The species E of sets
The species C of cyclical orderings (cycles/rings)
Only put a structure on underlying sets whose size satisfies the predicate.
Only put a structure on underlying sets of the given size. We
include this as a special case, instead of just using
(==k), since it can be more efficient: we get to turn infinite
lists of coefficients into finite ones.
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.
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
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.
Some derived operations on species.
Combinatorially, the operation of pointing picks out a
distinguished element from an underlying set. It is equivalent
to the operator
Some species that can be defined in terms of the primitive species operations.
The species L of linear orderings (lists): since lists are isomorphic to cycles with a hole, we may take L = C'.
Structures of the species eps of elements are just elements of the underlying set: eps = X * E.
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.
The species Bal of ballots consists of linear orderings of nonempty sets: Bal = L o E+.