Hi,
In Python (hence Sage) there exist simple aggregate or
enumerative
structures: dictionaries, lists (and tuples), and sets.
Beyond
these types, there are Sage Sequences and Sets, and (name
under
discussion) EnumeratedSets coming from the combinatorial
community.
For comparison, in Magma one has classes for sequences, sets,
and
indexed sets (which combine the indexing of sequences with
hashed
set structure). Since Magma invents its own language
(generally
a negative), it makes its own choices about what datastructures
to
provide. This largely dictates the conventions for their use.
In
Sage, as these structures multiply, we need to decide what are
the
best datastructures to implement (beyond Python types) and
which
to
use.
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.
Ex. 3: Should we return an tuple, EnumeratedSet, or
Sequence?:
sage: P0 = PolynomialRing(QQ,list
("abc"))
sage: type(P0.gens
())
<type
'tuple'>
Ex. 4: This is of a slightly different flavour, but we
could
instead return a Sequence (which knows that all points
belong
to the same parent), or an EnumeratedSet (giving hashed
lookup
and
indexing):
sage: FF = FiniteField
(7)
sage: E = EllipticCurve([FF(1),FF
(3)])
sage: type(E.rational_points
())
<type
'list'>
The first two examples are different implementations of the
same
object (with different representations but they could
converge
into one FreeModule class with sparse and dense
subclasses).
The third example is similar, in the sense that a polynomial
ring
is a free object on the underlying set of generators, which
we
could define to be a basis. The last example is just another
instance of a naturally occurring, finite enumerable structure,
where we might want to preserve the knowledge of the common
parent (e.g. Magma would return a sequence or indexed set
which stores this data).
The important feature of a free object F(X) on a set X (in
a
category C) is
that:
Hom_Set(X,U(G)) = Hom_C(F
(X),G),
where U(G) is the underlying set of object G. This is just
the
definition of a free function F as left adjoint to the
forgetful
functor U. In practice, this means we would like to be
able
to pass a morphism of sets f in Hom_Set(X,U(G)) to the
homset
Hom_C(F(X),G) as defining data of a morphism F(X) ->
G.
In order to do so, it would be desirable, in the first
three
examples, to define F(X).basis() which return a Sage object
X
for which we can construct its morphisms (of sets). It
would
also be desirable for this basis to be efficient -- for
finite
X it should not involve too much overhead (compared with
a
Python tuple or list, or Sage
Sequence).
I see that a hierarchy of EnumeratedSet classes would give
a
common category for returning all sort of enumerable and
iterable
objects which can extend to infinite (enumerable)
sets.
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?)
Here F could be
a:
FreeGroup
FreeAbelianGroup
FreeMonoid
FreeAbelianMonoid
FreeModule
PolynomialRing (= Free[Unital]
CommutativeRing)
FreeAlgebra (=
FreeUnitalAssociativeAlgebra)
etc.
This supposes that the EnumeratedSet class is as
efficient,
intuitive, and useful for finite sets (with indexing) as
a
list, tuple, or Sequence. I assume that this class
belongs
to the category of sets, not ordered sets, and so that
the
indexing is not respected by morphisms. However, one
could
have the possibility of using the indexing to define a
set
morphism via a morphism of the index
sets.
This leaves open the question what roles Sequence and Set
play,
and whether the class Set can be superceded by
EnumeratedSet,
or where in the system they should be
used.
In short, I think we should decide what are the primary
aggregate
structures to support, optimise, and use, then set these down
as
conventions in the developers
guide.
Comments?
--David
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
