Math.Combinatorics.Species.Generate

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

Documentation

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

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 where

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]

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.