species-0.3.2.3: Computational combinatorial species

Stability experimental byorgey@cis.upenn.edu None

Math.Combinatorics.Species.AST

Description

Various data structures representing reified combinatorial species expressions. See also Math.Combinatorics.Species.AST.Instances.

Synopsis

# Basic species expression AST

data SpeciesAST whereSource

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

Constructors

 Zero :: SpeciesAST One :: SpeciesAST N :: Integer -> SpeciesAST X :: SpeciesAST E :: SpeciesAST C :: SpeciesAST L :: SpeciesAST Subset :: SpeciesAST KSubset :: Integer -> SpeciesAST Elt :: SpeciesAST :+ :: SpeciesAST -> SpeciesAST -> SpeciesAST :* :: SpeciesAST -> SpeciesAST -> SpeciesAST :. :: SpeciesAST -> SpeciesAST -> SpeciesAST :>< :: SpeciesAST -> SpeciesAST -> SpeciesAST :@ :: SpeciesAST -> SpeciesAST -> SpeciesAST Der :: SpeciesAST -> SpeciesAST OfSize :: SpeciesAST -> (Integer -> Bool) -> SpeciesAST OfSizeExactly :: SpeciesAST -> Integer -> SpeciesAST NonEmpty :: SpeciesAST -> SpeciesAST Rec :: ASTFunctor f => f -> SpeciesAST Omega :: SpeciesAST

Instances

 Eq SpeciesAST Species expressions can be compared for structural equality. (Note that if `s1` and `s2` are isomorphic species we do not necessarily have `s1 == s2`.) Note, however, that species containing an `OfSize` constructor will always compare as `False` with any other species, since we cannot decide function equality. Ord SpeciesAST An (arbitrary) `Ord` instance, so that we can put species expressions in canonical order when simplifying. 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 `Species` class, so we can use the Species class DSL to build species expression ASTs.

# Typed, sized species expression AST

data TSpeciesAST s whereSource

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.

Constructors

 TZero :: TSpeciesAST Void TOne :: TSpeciesAST Unit TN :: Integer -> TSpeciesAST (Const Integer) TX :: TSpeciesAST Id TE :: TSpeciesAST Set TC :: TSpeciesAST Cycle TL :: TSpeciesAST [] TSubset :: TSpeciesAST Set TKSubset :: Integer -> TSpeciesAST Set TElt :: TSpeciesAST Id :+:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (f :+: g) :*:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (f :*: g) :.:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (f :.: g) :><:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (f :*: g) :@:: :: SizedSpeciesAST f -> SizedSpeciesAST g -> TSpeciesAST (f :.: g) TDer :: SizedSpeciesAST f -> TSpeciesAST (f :.: Star) TOfSize :: SizedSpeciesAST f -> (Integer -> Bool) -> TSpeciesAST f TOfSizeExactly :: SizedSpeciesAST f -> Integer -> TSpeciesAST f TNonEmpty :: SizedSpeciesAST f -> TSpeciesAST f TRec :: ASTFunctor f => f -> TSpeciesAST (Mu f) TOmega :: TSpeciesAST Void

Instances

 Show (TSpeciesAST s)

## Size annotations

data SizedSpeciesAST s whereSource

Constructors

 Sized :: Interval -> TSpeciesAST s -> SizedSpeciesAST s

Given a `TSpeciesAST`, compute (a conservative approximation of) the interval of label set sizes on which the species yields any structures.

Annotate a `TSpeciesAST` with the interval of label set sizes for which it yields structures.

Retrieve the interval annotation from a `SizedSpeciesAST`.

Strip the interval annotation from a `SizedSpeciesAST`.

## Existentially wrapped AST

data ESpeciesAST whereSource

An existential wrapper to hide the phantom type parameter to `SizedSpeciesAST`, so we can make it an instance of `Species`.

Constructors

 Wrap :: Typeable1 s => SizedSpeciesAST s -> ESpeciesAST

Instances

 Show ESpeciesAST C ESpeciesAST C ESpeciesAST C ESpeciesAST Species ESpeciesAST

Construct an `ESpeciesAST` from a `TSpeciesAST` by adding an appropriate interval annotation and hiding the type.

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 the type and interval information from an existentially wrapped species AST.

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

Reconstruct the type and interval annotations on a species AST.

# ASTFunctor class (codes for higher-order functors)

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.

Methods

apply :: Typeable1 g => f -> TSpeciesAST g -> TSpeciesAST (Interp f g)Source

# Miscellaneous AST operations

`needsCI` is a predicate which checks whether a species expression uses any of the operations which are not supported directly by ordinary generating functions (composition, differentiation, cartesian product, and functor composition), and hence need cycle index series.

substRec :: ASTFunctor f => f -> SpeciesAST -> SpeciesAST -> SpeciesASTSource

Substitute an expression for recursive occurrences.