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

- generateF :: SpeciesAlgT s -> [a] -> [StructureF s a]
- data Structure a where
- generate :: SpeciesAlg -> [a] -> [Structure a]

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

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.

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.