Math.Combinatorics.Species.AST

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

Basic species expression AST

data SpeciesAST where

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

B :: 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

Typed, sized species expression AST

data TSpeciesAST s where

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

TB :: TSpeciesAST Bracelet

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

Size annotations

data SizedSpeciesAST s where

Constructors

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

interval :: TSpeciesAST s -> Interval

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

annI :: TSpeciesAST s -> SizedSpeciesAST s

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

getI :: SizedSpeciesAST s -> Interval

Retrieve the interval annotation from a SizedSpeciesAST.

stripI :: SizedSpeciesAST s -> TSpeciesAST s

Strip the interval annotation from a SizedSpeciesAST.

Existentially wrapped AST

data ESpeciesAST where

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

Constructors

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

wrap :: Typeable s => TSpeciesAST s -> ESpeciesAST

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

unwrap :: Typeable s => ESpeciesAST -> TSpeciesAST s

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

Erase the type and interval information from an existentially wrapped species AST.

erase' :: TSpeciesAST f -> SpeciesAST

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

annotate :: SpeciesAST -> ESpeciesAST

Reconstruct the type and interval annotations on a species AST.

ASTFunctor class (codes for higher-order functors)

class (Typeable f, Show f, Typeable (Interp f (Mu f))) => ASTFunctor f where

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.

Minimal complete definition

apply

Methods

apply :: Typeable g => f -> TSpeciesAST g -> TSpeciesAST (Interp f g)

Miscellaneous AST operations

needsCI :: SpeciesAST -> Bool

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

Substitute an expression for recursive occurrences.