Waldek Hebisch <[EMAIL PROTECTED]> writes:
> You "It is a design decision", but my question is what you gain doing
> computations at type level as opposed to computiong at element level.
I'm not sure whether my previous post was overlooked or unclear. So, I repeat
it (below) and try to make it clearer by elaborating:
When Nicolas Thiery presented MuPAD Combinat (which is really a great piece of
software), a fundamental design problem became apparent.
* on the one hand, there are combinatorial objects which are *mainly* (at
least, at first sight) interesting for looking at them, eg. Dyck paths. It
does not seem worth the effort to have a domain "Dyck Path", just for
generating all the trees with 5 elements.
* on the other hand, there are some objects, which are very naturally elements
of a domain, like permutations, lists, or sets.
In MuPAD combinat, in the end they decided to go mainly for the first option:
there is a (huge) domain-package "DecomposableObjects", with a function that
takes a grammar and (roughly) returns the objects of the language the grammar
describes.
Ralf and I were not completely happy with this approach. It somehow didn't fit
our picture how design in Aldor should work. Then we discovered the species
framework, and found that it would fit quite well.
> AFAICS at practical level you do not need sets: only number of elements
> matter (plus ability to "lift" permutations). Numbers and permutations live
> in ordinary world, so why you go to type level?
Hm, I think that's exactly what we do: permutations are elements of the domain
Permutation. This domain in turn is a species. I do not think that you
believe that, but just to make sure: we do not consider a single permutation as
a domain.
So, what do we gain by introducing the set of Dyck paths, or any other species,
as a separate domain instead of simply considering species as elements of a
single domain -- which we do additionally?
One advantage is that it's "nicer" and more uniform. To define binary trees,
you can write
macro {
X == SingletonSpecies;
+ == Plus;
* == Times;
}
B(L: LabelType): CombinatorialSpecies L == (X + B*B)(L) add;
structures(set [1,2,3,4])$B(Integer);
generatingSeries$B(Integer);
(side remark: I have not yet stopped thinking about allowing something like
generatingSeries$B
since obviously, the label type is irrelevant to the generatingSeries.)
That is, you can give your grammar at the top level. In the other approach,
you would have to give the grammar to a wrapper function, which then generates
the objects:
BinTree := grammar(B=X+B*B)
and you would then have methods to generate them, find the generating functions
etc.:
structures([1,2,3,4], BinTree)
generatingSeries(BinTree)
But this doesn't integrate nicely with permutations, lists or sets, where
natural Aldor/Axiom domains exist. (It can be done, as MuPAD-combinat shows,
just, it doesn't feel right to us.) Personally, I like it a lot that the data
structure is really part of the species, and that the operations on species do
not depend on this data structure.
Another advantage is that all the operations on species (Plus, Times,
Composition, Functorial Composition, etc.) can exist (more or less)
independently of each other. The programming becomes very modular, even in
practice: I hardly touched Functorial Composition, but put a lot of effort into
(partitional) composition. Nicolas Thiery told us that this became quite a
problem with their approach.
I should stress that I'm well aware of the fact that our approach is not the
only one and might not be the most efficient. But so far, it feels really
good. Especially to me (less so to Ralf), the two reasons I just gave were not
very convincing at the beginning. But I think it was the right decision. I'm
already very curious how I'll think about this when we have implemented
multivariate species...
Does this answer your question?
Martin
attached my previous post.
> > > If the goal is to implement species theory I would probably start:
> > >
> > > SemiRing():Category == ....
> > >
> > > SpeciesRingCategory():Category == SemiRing with -- add extra
> > > operations like composition and differential ....
>
> That's only half of the story, namely where you regard the collection of all
> species. But of course, the species of permutations is a useful domain, too:
> on the one hand, I want to be able to work with objects that are permutations,
> on the other hand, I want to work with the species of permutations as an
> object. In our project, we reach this goal. In fact, we do have a proof of
> concept implementation of SpeciesRing, where the objects are then the various
> species, i.e., Rep is CombinatorialSpecies(L).
>
>
> > > Also, it would help if you say what combinat can do. Looking at code
> > > I see that it can compute generating functions. It seems that you
> > > also have code to enumerate corresponding sets, but it is not clear
> > > what is the result: if I have species of permutations can I compose
> > > resulting permutations?
>
> All of that. If you are not concerned about speed, you can define the domain
> Permutation as Compose(SetSpecies, Cycle).
>
> structures set [a,b,c,d]
>
> will then give the 24 permutations. And it is not difficult to (aldor-)extend
> this domain to include all the usual operations on permutations you want, like
> composition, inversion, etc.
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Aldor-combinat-devel mailing list
Aldor-combinat-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/aldor-combinat-devel
