[Axiom-developer] Re: Combinat

[Ralf Hemmecke]

> I've been studying your combinatorial species project.

> Would it be reasonable to say that one could redefine (some of) the 
> data structures in axiom using a series of transformations and 
> combinations on sets?

I would say, yes. It would not be every data structure though. One could
define List as

List(L: LabelType): CombinatorialSpecies L ==
  Plus(EmptySetSpecies, Times(SingletonSpecies, List))(L) add {...}

the {...} is needed because the usual List has a few more exports.

But List is actually rather special and should be implemented in a more
efficient way.

But yes, species can be considered as a generic way to build data
structures. And one would get their generating series and a generation
of all structures of a certain size as a "side effect" that does not 
need any more effort than writing the "equation" as above for List.

> Would it be a set of pointers?

No. No pointers involved. Everything is fully and statically typed.

> So a species is a "builder function" that would build a given data
> structure, like a linked list, from a set of pointers?

Builder function is correct. Pointers is wrong. If you have the 
construction as above you would says

for l in structures set [1,2,3,4] repeat stdout << l << newline;

and it will print all the 4! different lists of with 4 elements.

(But you see List is rather special, I actually need it already to form 
the input of the "structures" function. But take

1 ==> EmptySetSpecies;
X ==> SingletonSpecies;
+ ==> Plus;
* ==> Times;
B(L: LabelType): CombinatorialSpecies L == (1+X*B*B)(L) add {...}

and the same "for" loop above with structures$B gives you all binary 
rooted trees with exactly 4 nodes.

Hope that helps.
Ralf