Structures and IsomorphismTypes: MultiSet

Let me respond to my own posting...

I've now read the section on multi-sort species again, and begin to
understand that these "structure types inbetween" (which come from
multiset input) are, in fact, ordinary isomorphism types of multi-sort
species. For that reason there is another "con" which actually has
nothing to do with the order on L.

It rather says that introducing multisets in a unisort species context
I consider not my _favourite_ design.

1) Multisort species come with different generating series (having as
many variables as the number of sorts).

2) Although the generation of structures might be more efficient if done
in the way Martin does it in branches/iso-experiment, having unisort and
multisort concepts in one context, is not what I would prefer.

3) It seem a bit cumbersome to require the user to call

structures([l11,l12],[l21]) $ BinaryTree(L1,L2)

for generating, for example, isomorphism types of trees with 3 nodes
where two of them are indistinguishable and

structures([l11,l12],[l21],[l31,l32,l33]) $ BinaryTree(L1,L2,L3)

for an analogous thing.

That sounds like introducing lots and lots of domains and making it hard
to work with AC.

4) However, if I consider functorial composition (BLL right after
Example 2.4.9) then having

MULTISORTSPECIES ==> (L: Tuple(LabelType)) -> CombinatorialSpecies(L)

(note the "Tuple")
would not be such a bad idea.

BTW, I am not saying that I am completely against

structures: MultiSet L -> Generator %

because it would perhaps mean that we switch to implement multi-sort
species, but what bothers me are the generating series. They are then
simply not "multi-sort". So if someone tells me how that can be
resolved, I'd be more happy.

Ralf

Post by Ralf Hemmecke
Hello to all who care...
I would like to take up the diskussion started at
http://thread.gmane.org/gmane.comp.mathematics.aldor-combinat.devel/537
In particular I'd like to discuss the design of the generation of
structures and isomorphism types.
Actually, Martin made me aware of the fact that there are not only
labelled and unlabelled structures but also things inbetween. So
structures: MultiSet L -> Generator %
would be a good candidate for a new design.
If all elements have multiplicity 1, then it would be like
structures: SetSpecies L -> Generator %
And if there is only one element with multiplicity n, then it would be like
isomorphismTypes: SetSpecies -> Generator %.
In fact, I believe that for a cleaner interface both of the functions
involving "SetSpecies" should not be exported but rather only used
internally.
Currently, I see a MultiSet(L) as something like a polynomial domain
(that has no multiplication, and all elements are of "degree" 1) where
the "variables" are from L and the (non-negative integer) coefficients
denote the multiplicity of the "variable".
Now, since there is a domain "SparseAdditiveArray" in AC that basically
is such a "polynomial domain of degree 1", it costs not much to
implement MultiSet.
What bothers me a bit is whether L should be ordered or not.
There are pros and cons.
con 1) A multiset is by nature unordered.
con 2) We deal with species that work over sets.
con 3) I don't yet have an idea whether ordering the "variables" would
cost a lot in the generation of species.
pro 1) SparseAdditiveArray works only with ordered "variables".
pro 2) I believe that introducing some order on the input is necessary
for (un)ranking anyway.
pro 3) Since species are endofunctors of the finite sets category,
ordering (of a finite set) is not a big deal.
I think the code that Martin has in branches/iso-experiments could serve
as a start for the idea of having only
structures: MultiSet L -> Generator %
Does somebody see any problem in that design?
Ralf

-------------------------------------------------------------------------
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

Martin Rubey

2007-03-01 15:41:39 UTC

Dear Ralf,

Post by Ralf Hemmecke
I've now read the section on multi-sort species again, and begin to
understand that these "structure types inbetween" (which come from multiset
input) are, in fact, ordinary isomorphism types of multi-sort species. For
that reason there is another "con" which actually has nothing to do with the
order on L.

Yes, that's also my view.

Post by Ralf Hemmecke
It rather says that introducing multisets in a unisort species context I
consider not my _favourite_ design.

I'd consider MultiSorted species as a necessary generalization in order to have
a clean design for isomorphism types.

Post by Ralf Hemmecke
1) Multisort species come with different generating series (having as many
variables as the number of sorts).
2) Although the generation of structures might be more efficient if done in
the way Martin does it in branches/iso-experiment, having unisort and
multisort concepts in one context, is not what I would prefer.
3) It seem a bit cumbersome to require the user to call
structures([l11,l12],[l21]) $ BinaryTree(L1,L2)
for generating, for example, isomorphism types of trees with 3 nodes where
two of them are indistinguishable and
structures([l11,l12],[l21],[l31,l32,l33]) $ BinaryTree(L1,L2,L3)

I think it would be quite OK to restrict ourselves to the case where the
(aldor-) types of the labels are all the same. Thus, we'd only have
BinaryTree L, just as we do now.

This is not really a restriction, since one can always use a union type, in
case one insists on having some labels being strings, other being numbers.

In fact, this justifies most of my design a posteriori, except for the fact
that I introduced new domains for the multisorted context.

Post by Ralf Hemmecke
I am not saying that I am completely against
structures: MultiSet L -> Generator %
because it would perhaps mean that we switch to implement multi-sort species,
but what bothers me are the generating series. They are then simply not
"multi-sort".

we really should strive to have multisorted series, too.

However, maybe we could - for the moment - just switch to multisorted
structures, and leave the series as they are.

Actually, Martin made me aware of the fact that there are not only labelled
and unlabelled structures but also things inbetween. So
structures: MultiSet L -> Generator %
would be a good candidate for a new design.
If all elements have multiplicity 1, then it would be like
structures: SetSpecies L -> Generator %
And if there is only one element with multiplicity n, then it would be like
isomorphismTypes: SetSpecies -> Generator %.
In fact, I believe that for a cleaner interface both of the functions
involving "SetSpecies" should not be exported but rather only used
internally.

I don't know about that one. In any case, it seems obvious to me that it should
be possible to provide special implementations and representations for the
special cases of labelled and unlabelled (univariate) structures.

Currently, I see a MultiSet(L) as something like a polynomial domain (that
has no multiplication, and all elements are of "degree" 1) where the
"variables" are from L and the (non-negative integer) coefficients denote
the multiplicity of the "variable".

Isn't that an implementation detail?

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

Martin Rubey

2007-03-01 21:43:25 UTC

Dear Ralf,

Post by Martin Rubey
I'd consider MultiSorted species as a necessary generalization in order to
have a clean design for isomorphism types.

I just remembered that, when I started implementing iso-experiment, I thought
about the relationship to MultiSorted species.

And I came to the conclusion - I believe - that I would cover only a part of
MultiSorted species, but I am not so sure anymore.

Ralf, did you check?

In particular, I think generating labelled structures of several sorts is not
covered by my approach.

Post by Martin Rubey
I've now read the section on multi-sort species again, and begin to
understand that these "structure types inbetween" (which come from multiset
input) are, in fact, ordinary isomorphism types of multi-sort species.

More thinking needed...

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

Ralf Hemmecke

2007-03-01 23:22:09 UTC

Post by Martin Rubey
Dear Ralf,

Post by Martin Rubey
I'd consider MultiSorted species as a necessary generalization in order to
have a clean design for isomorphism types.

I just remembered that, when I started implementing iso-experiment, I thought
about the relationship to MultiSorted species.
And I came to the conclusion - I believe - that I would cover only a part of
MultiSorted species, but I am not so sure anymore.
Ralf, did you check?

I'd be happy if you could be more clear in your questions. So let me guess.

As far as I have seen, in branches/iso-experiment you work with unisort
species but you allow isomorphismTypes to take a multiset input. This,
indeed, cover not everything.

Of course, one could say that L is the disjoint union of all sorts and
have just one L in the argument of CombinatorialSpeciesCategory, but I
somehow have the feeling there will go something wrong when it comes to
functorial composition F \square (G_1, ..., G_n). Not that I have
completely thought that through, but I guess that changing the argument
from LabelType to Tuple(LableType) would be more appropriate.

Maybe as a next thing I should take the exercise of implementing
(unisort) functorial composition. I believe when I started to design how
species should look like in Aldor, I thought also of functorial
composition. And if I am not completely wrong then is will simply start like

FuntorialCompose(F: SPECIES, G: SPECIES)(L: LabelType):
CombinatorialSpeciesCategory L == add {
Rep == F(G(L));
...
}

As you see here, the CombinatorialSpeciesCategory(L) should export
LabelType. It says nothing more than "a structure can serve as a label".
And we already use it in "Compose(F,G)". Its representation is

Rep == Record(
tag: Partition L,
left: F SetSpecies L,
right: SetSpecies G L
);

For multisort species I want similar simple constructions.

Post by Martin Rubey
In particular, I think generating labelled structures of several sorts is not
covered by my approach.

Only through mapping (multisort) labels to integer, generating iso types
and mapping back.

In fact, I would not throw away your code, because basically you
implemented the ground algorithm which must be adapted to multisort.
(Whatever we decide what "multisort" should look like in AC.)

Ralf

-------------------------------------------------------------------------
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

Martin Rubey

2007-03-02 09:38:35 UTC

Post by Ralf Hemmecke
As far as I have seen, in branches/iso-experiment you work with unisort
species but you allow isomorphismTypes to take a multiset input. This,
indeed, cover not everything.

Yes. In Categorial Language, I have functors from the category of multisets
with bijections to the category of sets with bijections, I
guess.

Unfortunately, BLL use "multiensemble" (in french, what do they use in
english?) for something different, namely, a k-tuple of sets. A k-multisorted
species is a functor from the category of k-tuples of sets and bijections to
the category of sets with bijections...

So, my thing seems to be quite disjoint from multisort species. Only certain
cases of isomorphismtypes coincide, as you have noted. (But I didn't check)

Post by Martin Rubey
In particular, I think generating labelled structures of several sorts is
not covered by my approach.

Only through mapping (multisort) labels to integer, generating iso types and
mapping back.

???

Post by Ralf Hemmecke
In fact, I would not throw away your code, because basically you implemented
the ground algorithm which must be adapted to multisort. (Whatever we decide
what "multisort" should look like in AC.)

I didn't intend to throw away my code. I think it's quite ok. And in fact, very
likely we will need - to generate isomorphismtypes of compositions of
multisorted species - functors from the category of k-tuples of multisets to
the category of sets...

Post by Ralf Hemmecke
Of course, one could say that L is the disjoint union of all sorts and have
just one L in the argument of CombinatorialSpeciesCategory, but I somehow
have the feeling there will go something wrong when it comes to functorial
composition F \square (G_1, ..., G_n). Not that I have completely thought
that through, but I guess that changing the argument from LabelType to
Tuple(LableType) would be more appropriate.

I don't think so, but I guess, only time will tell.

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

Ralf Hemmecke

2007-03-02 11:11:25 UTC

Post by Martin Rubey
Yes. In Categorial Language, I have functors from the category of multisets
with bijections to the category of sets with bijections, I
guess.

Maybe.

Post by Martin Rubey
Unfortunately, BLL use "multiensemble" (in french, what do they use in
english?) for something different, namely, a k-tuple of sets. A k-multisorted
species is a functor from the category of k-tuples of sets and bijections to
the category of sets with bijections...

Ha, it seems you stepped over the same problem as me. ;-) For some time
I was wondering, why they call something like "k-tuple of sets" a
"k-multiset". I could not see equal elements. After a while I realized
that if you have a BLL-multiset U1+U2+...+Uk and factor out any
permutations of the components, you basically make all elements of U1
equal (same for U2,...,Uk). And that is a multiset as we are used to it.

Post by Martin Rubey
So, my thing seems to be quite disjoint from multisort species. Only certain
cases of isomorphismtypes coincide, as you have noted. (But I didn't check)

Post by Martin Rubey
In particular, I think generating labelled structures of several sorts is
not covered by my approach.

Only through mapping (multisort) labels to integer, generating iso types and
mapping back.

???

Let us just take the multiset {1^3, 2^2} which you can treat.
If I have a BLL-multiset ({a,b,c},{A,B}), I simply map it to your
multiset and then replace 1 by a and 2 by A. (But perhaps, b, c and B
should also appear in the result.)

Rather, a multisort species M is a functor M: B^k -> B. (k-tuples of
"sets", not "multisets")

I don't think so, but I guess, only time will tell.

How does M: B^k -> B look like to you?

Ralf

-------------------------------------------------------------------------
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

Martin Rubey

2007-03-02 11:53:33 UTC

Post by Martin Rubey
Yes. In Categorial Language, I have functors from the category of multisets
with bijections to the category of sets with bijections, I
guess.

Maybe.

Ha, it seems you stepped over the same problem as me. ;-) For some time I was
wondering, why they call something like "k-tuple of sets" a "k-multiset". I
could not see equal elements. After a while I realized that if you have a
BLL-multiset U1+U2+...+Uk and factor out any permutations of the components,
you basically make all elements of U1 equal (same for U2,...,Uk). And that is a
multiset as we are used to it.

YES! Good remark.

Post by Ralf Hemmecke
In fact, I would not throw away your code, because basically you
implemented the ground algorithm which must be adapted to
multisort. (Whatever we decide what "multisort" should look like in AC.)

I didn't intend to throw away my code. I think it's quite ok. And in fact,
very likely we will need - to generate isomorphismtypes of compositions of
multisorted species - functors from the category of k-tuples of multisets
to the category of sets...

Rather, a multisort species M is a functor M: B^k -> B. (k-tuples of "sets",
not "multisets")

Yes, but:

to generate isomorphismtypes of unisort species I need to be able to produce
structures with labels from a (usual) multiset.

It is highly unlikely that this is not necessary for multisort species. Thus,
we really need functors

MultiSet^k -> B

(It is "highly unlikely", since for k=1 we have the current situation. However,
it may well be the case that I overlooked something and composition can be done
without considering multisets. On the other hand, this generalisation looks
quite interesting to me!)

Post by Ralf Hemmecke
How does M: B^k -> B look like to you?

I don't understand this question.

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

Ralf Hemmecke

2007-03-01 17:55:49 UTC

Unfortunately my mail from 16:09:00 today did not get through due to
problem with my provider. :-( So here it comes again.
-----------------------------------------------------------
I've just read about linear species.

They don't look like a big deal from the design point of view.
The only thing that bothers me that there is a (ordinari) species of
permutation and a linear one and it would be a pity to call them by
different names.

Anyway, being now mildly familiar with the introction to multisorted and
linear species, I think that the best choice for structures is

structures: SetSpecies L -> Generator %.

However, in order to make ranking/unranking corresponding to the
generation of structures, I like to introduce an order on the set L of
labels, ie.,

define LabelType: Category == TotallyOrderedType with {
...
}

Using this order, it is straightforward to say that

structures set [1,2,3]

and

structures set [2,1,3]

generate the same structures in the same order.

If someone gets head aches with this (it basically says that SetSpecies
is a "sorted set"), then give some better suggestions. I would be happy
if someone finds the time to respond to my thoughts anyway. -- I feel
soo alone. ;-)

Ralf

-------------------------------------------------------------------------
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

Martin Rubey

2007-03-01 19:08:36 UTC

Post by Ralf Hemmecke
I've just read about linear species.
They don't look like a big deal from the design point of view. The only
thing that bothers me that there is a (ordinary) species of permutation and a
linear one and it would be a pity to call them by different names.

I think it would be a great thing if we'd be able to somehow transform ordinary
species into linear species.

As I said before, in the labelled case, this should be easy.

Why should it be a problem to have Permutation by a CombinatorialSpecies and a
LinearSpecies, by the way?

Post by Ralf Hemmecke
Anyway, being now mildly familiar with the introction to multisorted and
linear species, I think that the best choice for structures is
structures: SetSpecies L -> Generator %.

good.

Post by Ralf Hemmecke
However, in order to make ranking/unranking corresponding to the
generation of structures, I like to introduce an order on the set L of
labels, ie.,
define LabelType: Category == TotallyOrderedType with {
...
}
Using this order, it is straightforward to say that
structures set [1,2,3]
and
structures set [2,1,3]
generate the same structures in the same order.

Yes that sounds reasonable. It is probably better than introducing an
OrderedSet (aka List...) as I proposed at the very beginning of this project.

By the way, couldn't we drop the "Species" from SetSpecies then?

I hope, it is always possible to give a set some order... (Not only in theory)

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

Ralf Hemmecke

2007-03-01 20:18:55 UTC

Post by Ralf Hemmecke
linear species.
They don't look like a big deal from the design point of view. The only
thing that bothers me that there is a (ordinary) species of permutation and a
linear one and it would be a pity to call them by different names.

I think it would be a great thing if we'd be able to somehow transform ordinary
species into linear species.

I didn't dare to write it, but I had a similar idea even before I read
Remark 5.1.5. (which basically says that one can define a linear species
G from an ordinary species F by G[U, <] := F[U]).

Looks like a "coerce" ;-), but note that I would really make the type of
G different from F. First, it is a different type mathematically:
F: B -> B, G: L -> B
(where B is the category of finite sets and bijections and L is the
category of finite ordered sets and increasing bijections (isomorphisms
of ordered sets).
And second, there is no point in exporting "isomorphism types" in
LinearSpeciesCategory since "structures" agree with "isomorphismTypes".
(There is only one increasing bijection between two ordered n-sets.)

Post by Martin Rubey
As I said before, in the labelled case, this should be easy.

There is no "unlabelled" case in a linear species context.

Post by Martin Rubey
Why should it be a problem to have Permutation by a CombinatorialSpecies and a
LinearSpecies, by the way?

If I am not wrong, then Aldor should allow

Permutation(L: LabelType): CombinatorialSpeciesCategory L == add ...

and

Permutation(L: LabelType): LinearSpeciesCategory L == add ...

since each of the above "Permutation" has a different type.

There are two problems that I think will make this option not so well
suited.

1) If the is a "import from Combinat" then both versions are in scope
and if you then "import from Permutation(Integer)", it is not clear
which one is meant. I don't even recall whether

import from Permutation(Integer)@LinearSpeciesCategory(Integer);

would work. (I guess not.)

2) The current Aldor compiler produces garbage with such a construction.