Safe Haskell | None |
---|---|
Language | Haskell2010 |
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
- bracelets :: 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 Typeable (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 (f :+: g) a
- data (f :*: g) a = (f a) :*: (g a)
- data (f :.: g) a = Comp {
- unComp :: f (g a)
- data Star a
- newtype Cycle a = Cycle {
- getCycle :: [a]
- newtype Bracelet a = Bracelet {
- getBracelet :: [a]
- newtype Set a = Set {
- getSet :: [a]
- data SpeciesAST
- reify :: SpeciesAST -> SpeciesAST
- reflect :: Species s => SpeciesAST -> s
- data TSpeciesAST s
- data ESpeciesAST
- wrap :: Typeable s => TSpeciesAST s -> ESpeciesAST
- unwrap :: Typeable 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, Typeable (Interp f (Mu f))) => ASTFunctor f where
- apply :: Typeable 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 where Source
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
.
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 of bracelets (i.e. cycles that can also be flipped).
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
ksubset :: Integer -> s Source
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 `o` g)
-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
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 @@ g)
-structure
consists of an f
-structure on the set of all g
-structures.
ofSize :: s -> (Integer -> Bool) -> s Source
Only put a structure on underlying sets whose size satisfies the predicate.
ofSizeExactly :: s -> Integer -> s Source
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 -> s Source
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 -> s Source
A convenient synonym for differentiation.
-structures look like oneHole
ff
-structures on a set formed by adjoining
a distinguished "hole" element to the underlying set.
Derived operations
Derived species
partitions :: Species s => s Source
permutation :: Species s => s Source
A permutation is a set of disjoint cycles:
.permutation
= set
`o` cycles
permutations :: Species s => s Source
A permutation is a set of disjoint cycles:
.permutation
= set
`o` cycles
simpleGraph :: Species s => s Source
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 => s Source
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)
directedGraph :: Species s => s Source
directedGraphs :: Species s => s Source
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 !!
ns
-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 !!
ns
-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 Typeable (StructTy f) => Enumerable f where Source
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 Bracelet | |
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 ((:.:) f g) | |
(Enumerable f, Enumerable g) => Enumerable ((:*:) f g) | |
(Enumerable f, Enumerable g) => Enumerable ((:+:) f g) |
structureType :: ESpeciesAST -> String Source
returns a String representation of the
functor type which represents the structure of the species structureType
ss
.
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.
(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.
Bracelet structure. A value of type
is implemented as
Bracelet
a[a]
, but thought of as an undirected cycle (i.e. equivalent up
to rotations as well as flips/reversals).
Bracelet | |
|
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 structural equality.
(Note that if 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 -> SpeciesAST Source
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 -> s Source
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 :: Typeable s => TSpeciesAST s -> ESpeciesAST Source
Construct an ESpeciesAST
from a TSpeciesAST
by adding an
appropriate interval annotation and hiding the type.
unwrap :: Typeable s => ESpeciesAST -> TSpeciesAST s Source
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 -> SpeciesAST Source
Erase the type and interval information from an existentially wrapped species AST.
erase' :: TSpeciesAST f -> SpeciesAST Source
Erase the type and interval information from a typed species AST.
annotate :: SpeciesAST -> ESpeciesAST Source
Reconstruct the type and interval annotations on a species AST.
Species simplification
simplify :: SpeciesAST -> SpeciesAST Source
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, Typeable (Interp f (Mu f))) => ASTFunctor f where Source
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 :: Typeable 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 s Source
tries to compute the recursive species
represented by the code newtonRaphsonRec
f kf
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 -> s Source
Given a species r
and a desired accuracy k
,
computes a species which has contact at least newtonRaphson
r kk
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 forMyType
(and various other supporting things like a code and anASTFunctor
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).