Bonjour Francois,
I would like to draw your attention to a project of Ralf Hemmecke (RISC -
University of Linz) and mine.
Since May last year we have developed a "true" implementation of combinatorial
species. Meanwhile, it is nearly feature complete as far as ordinary species
(i.e., functors from Sets to Sets) are concerned.
We currently cover F+G, F*G, FoG, F', F\square G,
where, of course, for functorial composition we do not know of any algorithm to
produce the isomorphism types, neither for Hadamard product... (Do you?)
Our main objective was to design the package in such a way that it follows as
closely as possible the theory as developed in your book. As an example, to
define binary trees, one can write
macro {
E == EmptySetSpecies;
X == SingletonSpecies;
+ == Plus;
* == Times;
}
A(L: LabelType): CombinatorialSpecies L == (E + X*A*A)(L) add;
and obtains
structures
isomorphismTypes
generatingSeries
isomorphismTypeGeneratingSeries
cycleIndexSeries.
It is easily possible to "use" the structures one obtains. For example, it is
almost trivial (to anybody who knows Aldor, the programming language) to write
a function that spits out the height of a given binary tree:
(I leave 4 lines of technical details here
A(L: LabelType): CombinatorialSpecies L with {
height: % -> Integer;
} == Plus(SingletonSpecies, Times(A, A))(L) add {
height(x: %): Integer == {
X := struct rep x;
-- if X is a Singleton, the height is zero
X case left => 0;
-- otherwise, we have to compare the height of the left and the right branch
1+max(height left X.right, height right X.right);
}
(Still, we are thinking about ways to make definitions as the above easier)
One of our next goals is to extend to multisorted species. Furthermore, we will
maybe implement a brute force algorithm to generate isomorphism types when no
efficient algorithm is known.
To use it, you need to install Aldor (and optionally Axiom). If you are
interested, we would be glad to help you set things up.
Are we going to meet in China / FPSAC 07?
All the best,
Martin
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Aldor-combinat-devel mailing list
Aldor-combinat-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/aldor-combinat-devel
