Re: FreeGroup and some thoughts about Free Objects in general
Nicolas M. Thiery
On Tue, Mar 02, 2010 at 09:10:16AM +0100, Tobias Columbus wrote:
> I am sorry, that we didn't manage to talk more intensely during the
> SAGE days, but I preferred spending my last afternoon at the
> sea. Apologizes for that...
Hmm, given how nice the Calanques are I sure was not standing a chance :-)
> Anyway, I decided to keep on bothering you -- now by mail.
I am glad to hear back from you! Please next time send your e-mail
directly to sage-devel or sage-combinat-devel next time (they are in
CC now): others will be interested in this discussion and you are
likely to get quicker feedback (I was on vacations last week).
> First of all I need some help with my implementation ;-)
> My FreeGroup passes all except two tests in the TestSuite.
> These failing tests are _test_elements and _test_pickling.
> For the latter one I cannot figure out what I have to implement to
> pass this test. I browsed some code of other parents and it seems
> that drops and loads are implemented in SageObject and work out of
> the box for other implementations. What might be the problem is that
> my code does not lie in the sage tree, but in some other folder.
I indeed bet that's the problem. I should have mentioned that I almost
always do this kind of development directly in the Sage source tree.
> But honestly I have no idea about that and I couldn't find any
> documentation in SAGE about cPickle.
http://docs.python.org/library/pickle.html
> The _test_elements fails again with _test_pickling and with
> _test_category. The test
>
> isinstance( self.an_element(),
> self.an_element().parent().ElementClass )
>
> fails. I have absolutely no idea, how to fix this.
> I tried adding methods _element_class, _element_class_ returning
> my FreeGroupElement class but this did not help.
Just use:
class FreeGroup(...):
...
Element = FreeGroupElement
and the element_class will be constructed for you (with proper
inheritance from the categories, which is what the test is complaining
about).
Alternatively, you can directly define the FreeGroupElement class
inside your parent:
class FreeGroup(...):
...
class Element(...):
...
> I attached, my not-so-well-documented code. I would be thankful, if
> you find some time to have a look or just point me to some place
> containing the appropriate documentation for my problems... I think
> my code works with any kind of generators and even so with
> infinitely many generators:
>
> sage: f = FreeGroup( NonNegativeIntegers() )
>
> sage: f.an_element()
> 0
>
> sage: f.one()
> 1
> TODO: This output is ambigous and there needs to be some better
> representation in this case.
Maybe elements should be represented as words (possibly with an option
for the user to choose from).
Some random thoughts:
- Please use _element_constructor_ rather than __call__. Actually, in
a first round, you might get away with the default
_element_constructor_ with the change above.
- With the above, you don't need anymore to inherit from
MultiplicativeGroupElement; Element should be enough. The category
will provide you with the appropriate code. You may want to use
ElementWrapper by the way, which will e.g. provide an equality test
for you.
- some_elements should return an iterable (e.g. a list) rather than
an iterator. We should add a generic test about this.
- I am not sure I would want a coerce map from another free group
with other generators.
- Define group_generators rather than gens
- _plain_generators() is equivalent to self.group_generators().keys()
- for `an_element`, you might want to return a more typical element
- for `some_elements`, you might want to only return 3-5 typical
elements (that will make the associativity tests faster)
I'll answer the rest in a separate e-mail.
Thanks for your work on this, and for beta testing all that framework ...
Best,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Nicolas M. Thiery
On Tue, Mar 02, 2010 at 09:10:16AM +0100, Tobias Columbus wrote:
> Now to something more conceptual:
> I thought a bit about generalizing Free Object constructions.
> I think there are actually some things that may be implemented on
> a very abstract level in a class "FreeObject" -- for example.
>
> First, elements of free objects are more or less strings.
> Currently I represent them as a list of tuples
>
> [ (<generator>,<power> ) ]
>
> Multiplication is just concatenation of lists, with some checks
> that the representation is reduced.
> If the free object is abelian, one could handle this by sorting
> the list after some order on the generators and by doing
> multiplication by a simple "merge" -- like in the merge-phases of
> merge-sort.
>
> With this construction, modules can be handled quite easily, too:
> A free module is a free abelian group with elements being lists
> [ (<coefficient>, <generator>) ]
> where the coefficients are from the base ring and not from ZZ.
>
> I am not so sure whether this representation works for rings,
> algebras and other objects with more than one inner operation,
> but I will think about that.
Thanks for your inspiring thoughts! Here is how I see the things now.
First, as you point out, free additive abelian semigroups / monoids /
groups are nothing more than NN, and ZZ-free modules respectively (I
am not sure we want to distinguish the free semigroups and free
monoids). Hence, the first steps would be to:
- Define CommutativeAdditiveGroups().free(gens) as
CombinatorialFreeModule(ZZ, gens)
- Implement a category SemiRings()
- Implement the SemiRing of positive (resp. non negative) natural numbers
Should those be called PositiveIntegers resp. NonNegativeIntegers,
extending the current NonNegativeIntegers which is just an enumerated set?
- Extend CombinatorialFreeModule to accept a semiring as base ring
This probably will require extending the categories Modules /
ModulesWithBasis / ... to accept a semiring as argument. Or instead
to define new categories SemiRingModules / ...?
This will be a good occasion to review all the methods of
CombinatorialFreeModule, and move up into the categories those that
do not depend on the data structure. And to see whether we want to
split a super class for FreeModule over a semiring (if it's just a
question of having a meaningless _negate_ method around, we can
leave things as is, at least for the moment).
- Define CommutativeAdditiveMonoids().free(gens) as
CombinatorialFreeModule(NonNegativeIntegers(), gens)
Next step: multiplicative abelian semigroups/monoids/groups. One way
would be to simply apply a functor constructing a multiplicative group
from an additive group, simply by delegating all multiplicative
operations to additive operations on the underlying group. There would
be a small overhead; I don't know how much we would care about it.
The other option would be to share the data structure by abstracting
away a super class of CombinatorialFreeModule (possibly just for
CombinatorialFreeModule.Element). While we are at it, we might want to
go the extra mile, and define a class whose instances are,
mathematically speaking, functions: A -> B (e.g. A is the set of names
of the generators and B is ZZ) taking a constant value
(e.g. ZZ.zero()) on all but a finite number of elements of A. The
storage is sparse, and the main operation is:
zip(f, element1, element2)
which returns the function: x -> f(element1(x), element2(x)), whose
main job is to handle the sparse representation.
I am not sure whether we want to share the data structure between the
abelian and non abelian cases, since in the abelian case we may prefer
a dictionary (as is done in CombinatorialFreeModule) rather than a
sorted list. Instead, we probably want to redo the same as above,
using words/lists as data structure.
Things like FreeAlgebras can simply be defined as
FreeMonoid(...).algebra() (with the latest sage-combinat patches). In
case we want to add further operations, we can do that by inheritance,
but I'll skip that for now.
> Anyway, one central property of free objects is the way one defines
> morphisms. There is a bijection between {set-mappings from the
> generators to some other object A} and {morphisms from the free
> object on these generators to the object A}. In my opinion this
> bijection may be implemented independent of the parent/category. The
> morphism is determined by the image of the generators and the
> morphism-properties. Now in the list- representation of elements
> this morphism-properties break down to applying the set-mapping
> generator by generator -- at least for monoids, groups and
> modules. And this seems to be independent of the category we are in.
We are heading at full steam toward operads here! I sure like that :-)
Besides there are several persons interested in implementing operads
in Sage. But that won't be instantaneous, and I don't have experience
yet on how useful this would be in practice for our problems. So I
vote for just implementing this by hand for the moment. With the
above, and since a morphism of free algebra can be constructed in two
steps (extension into monoid morphism; extension into module
morphism), there are just 4 types of morphisms to handle
(additive/multiplicative; commutative/non commutative).
> Regards and apologizes for this lengthy email
Well, mine is no shorter :-) I hope you are still on, even after it,
for taking over this very much needed project!