Dear David,
I'm glad you asked this because, this was planned to be my next
step. Remember, I not doing combinatoric but algebraic combinatorics. So that
after dealing with basic combinatorics, the next goal is algebra. One
direction toward this goal is Nicolas catorgoy framework, which should be
also discussed here...
So, now that you asked, I can give my answers without asking and answering at
the same time :-)
> Ex. 1: This is a Sage sequence
> class:
>
> sage: F0 = FreeModule(QQ,
> 3)
> sage: B0 = F0.basis
> ()
> sage: type
> (B0)
> <class
> 'sage.structure.sequence.Sequence'>
>
> and tuple for the same basis given by gens
> ()
>
> sage: type(F0.gens
> ())
> <type
> 'tuple'>
>
> Ex. 2: This is the EnumeratedSet
> class:
>
> sage: F1 = CombinatorialFreeModule(QQ, list
> ("abc"))
> sage: B1 = F1.basis
> ()
> sage: type
> (B1)
> <class
> 'sage.combinat.family.FiniteFamily'>
>
> Currently gens() is not
> implemented.
Note that this is a particular kind of family. Depending whether the
generating set is infinite, we switch to a different kind of family, with
different data structure. So that my first answer is, before choosing a data
structure optimize it, I'd rather try to gather all different use case to see
if we can find a common interface.
> As a start, I would suggest that for free objects F, one
> define
>
> F.basis() : EnumeratedSet X such that F = F
> (X)
> F.gens() : Python tuple when X is finite, or else an
> error
> (or should this be an immutable
> Sequence?)
Let me start with the problems I see in this design:
1) I dislike gens... A typical example currently studied by several people in
combinat is the algebra K[G] of a Coxeter group G, say the symmetric group. So
as a K-module, it is the free K module whose basis are the element of G. now
as an algebra it is generated by the elementary transpositions (i, i+1). So
that gens is far too ambiguous... So if you have generator, this is for a
particular category...
2) For technical reason (one object has only one parent) but also for
mathematical reason (see below) , we need to make the difference between the
generator in F an the indexing set X. Let me quote one of my previous e-mail
concerning free modules:
As usual in mathematics, we identify two different things, whereas when
writing code we have to be very precise. The universal property in the
category of R-module state that:
For any ring R and set E, there exist an unique (upto isomorphism) R-module
R(E), and a mapping i: E -> R(E) such that if f is an arbitrary mapping
from E to some R-module M, then there exists a unique module homomorphism
g: R(E) -> M such that f = g o i. The mapping i is called the canonical
injection from E to R(E).
Usually when speaking about R(E), we don't make any difference between any e
in E, and the corresponding element i(e) in R(E). The same abuse of language
is usually done in free group. This being clear, in R(E) there is a canonical
basis (i(e))_{e in E}. Please mind the canonical injection i in this formula.
Mathematically, it is important to distinguish between e and i(e) because
there are a lot of examples of module which are free and which have several
natural bases all indexed by the same set. Incidentally, this is one of our
principal work to find the best basis to understand a computation. So that we
keep playing with different bases.
Let's go back to the point: It took quite a time to Nicolas and I to realize
that the good notion is the notion of family (f_i)_{i in I}. Please have a
look at
sage.combinat.family.Family
This code is very new to sage, so it probably needs some polishing and
optimization. But I pretty convinced that this is the good design. We keep
doing this in maths without even thinking about it... Here is a more or less
python tuned of the design we had in MuPAD-combinat for my previous example of
K[G]. Let call it A.
1) as a free module there is a family, that is a particular case of
EnumeratedSet called A.basis().
- therefore A.basis().list() or equivalently list(A.basis()) return a list of
element of A.
- A.basis().keys() return the EnumeratedSet of element of the group G.
- if you have an element of G, you can ask A.basis()[G] to get the
corresponding element in A
2) as an algebra there is another family called A.algebra_generators() which
is the family (s_i := A((i, i+1)) )_{i=1..n-1} if we are in the algebra of
the symmetric group S_n.
- So A.algebra_generators().keys() is the set {1...n-1}. Note that we can
also index it by the transpositions themselves.
3) If we (and it seems that some people do) want to play in the algebra of
S_oo. There is nothing to change to the design ! The main difference is
that the family basis() and algebra_generators() are no more implemented by
a dictionary but by something more lazy.
I hope I managed to make myself clear... Please comment at will. As usual,
when we agreed, this should end on a wiki and finally in sage's doc.
Cheers,
Florent
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
