species-0.1: Combinatorial species library

Math.Combinatorics.Species.Generate

Description

Generation of species: given a species and an underlying set of labels, generate a list of all structures built from the underlying set.

Synopsis

# Documentation

generateF :: SpeciesAlgT s -> [a] -> [StructureF s a]Source

Given an AST describing a species, with a phantom type parameter describing the species at the type level, and an underlying set, generate a list of all possible structures built over the underlying set. Of course, the type of the output list is a function of the species structure. (Of course, it would be really nice to have a real dependently-typed language for this!)

Unfortunately, `SpeciesAlgT` cannot be made an instance of `Species`, so if we want to be able to generate structures given an expression of the `Species` DSL as input, we must take `SpeciesAlg` as input, which existentially wraps the phantom structure type---but this means that the output list type must be existentially quantified as well; see `generate` below.

data Structure a whereSource

An existential wrapper for structures. For now we just ensure that they are Showable; in a future version of the library I hope to be able to add a Typeable constraint as well, so that we can actually usefully recover the generated values if we know what type we are expecting.

Constructors

 Structure :: ShowF f => f a -> Structure a

Instances

 Show a => Show (Structure a)

generate :: SpeciesAlg -> [a] -> [Structure a]Source

We can generate structures from a `SpeciesAlg` (which is an instance of `Species`) only if we existentially quantify over the output type. However, we have guaranteed that the structures will be Showable. For example:

``` > generate octopi ([1,2,3] :: [Int])
[{{*,1,2,3}},{{*,1,3,2}},{{*,2,1,3}},{{*,2,3,1}},{{*,3,1,2}},{{*,3,2,1}},
{{*,1,2},{*,3}},{{*,2,1},{*,3}},{{*,1,3},{*,2}},{{*,3,1},{*,2}},{{*,1},
{*,2,3}},{{*,1},{*,3,2}},{{*,1},{*,2},{*,3}},{{*,1},{*,3},{*,2}}]
```

Of course, this is not the output we might hope for; octopi are cycles of lists, but above we are seeing the fact that lists are implemented as the derivative of cycles, so each list is represented by a cycle containing *. In a future version of this library I plan to implement a system for automatically converting between isomorphic structures during species generation.