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; 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, SpeciesTypedAST 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 SpeciesAST 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 and generateTyped below.

generate s ls generates a complete list of all s-structures over the underlying set of labels ls. 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>>]

 > generate subsets "abc"
 [{'a','b','c'},{'a','b'},{'a','c'},{'a'},{'b','c'},{'b'},{'c'},{}]

 > generate simpleGraphs ([1,2,3] :: [Int])
 [{{1,2},{1,3},{2,3}},{{1,2},{1,3}},{{1,2},{2,3}},{{1,2}},{{1,3},{2,3}},
  {{1,3}},{{2,3}},{}]

There is one caveat: since the type of the generated structures is different for each species, it must be existentially quantified! The output of generate can always be Shown, but not much else.

However! All is not lost. It's possible, by the magic of Data.Typeable, to yank the type information (kicking and screaming) back into the open, so that you can then manipulate the generated structures to your heart's content. To see how, consult structureType and generateTyped.

generateTyped s ls generates a complete list of all s-structures over the underlying set of labels ls, where the type of the generated structures is known (structureType may be used to compute this type). For example:

 > structureType subsets
 "Set"
 > generateTyped subsets ([1,2,3] :: [Int]) :: [Set Int]
 [{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{}]
 > map (sum . getSet) $ it
 [6,3,4,1,5,2,3,0]

Although the output from generate appears the same, trying to compute the subset sums fails spectacularly if we use generate instead of generateTyped:

 > generate subsets ([1..3] :: [Int])
 [{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{}]
 > map (sum . getSet) $ it
 <interactive>:1:21:
     Couldn't match expected type `Set a'
            against inferred type `Math.Combinatorics.Species.Generate.Structure
                                     Int'
       Expected type: [Set a]
       Inferred type: [Math.Combinatorics.Species.Generate.Structure Int]
     In the second argument of `($)', namely `it'
     In the expression: map (sum . getSet) $ it

If we use the wrong type, we get a nice error message:

 > generateTyped octopi ([1..3] :: [Int]) :: [Set Int]
 *** Exception: structure type mismatch.
   Expected: Set Int
   Inferred: Comp Cycle (Comp Cycle Star) Int

structureType s returns a String representation of the functor type which represents the structure of the species s. In particular, if structureType s prints "T", then you can safely use generateTyped by writing

 generateTyped s ls :: [T L]

where ls :: [L].