Opened 9 years ago
Closed 8 years ago
#15852 closed enhancement (fixed)
uncouple Sequence from categories
Reported by:  Ralf Stephan  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  categories  Keywords:  
Cc:  Nicolas M. Thiéry  Merged in:  
Authors:  Ralf Stephan  Reviewers:  Volker Braun 
Report Upstream:  N/A  Work issues:  
Branch:  1f9c338 (Commits, GitHub, GitLab)  Commit:  1f9c338257b8b551acb3038aae7014ad8c2abaa8 
Dependencies:  Stopgaps: 
Description (last modified by )
The class Sequence
is difficult to place in the categories, as the discussion in this ticket shows. Rather, it has its place as programming utility, probably in misc
. Thus, it needs not have a parent nor a category, nor mathematical operations like +, ... This ticket will deprecate/remove the corresponding methods.
Previous description:
The category Sequence
is deprecated since 2009 (commit 619aa0fa
). If I understand it correctly, the class Sequence
should instead have a parent from the category Sets
.
The ticket that will remove category Sequence
depends on this.
Change History (39)
comment:1 Changed 9 years ago by
Description:  modified (diff) 

comment:2 Changed 9 years ago by
Branch:  → u/rws/ticket/15852 

Created:  Feb 23, 2014, 5:52:58 PM → Feb 23, 2014, 5:52:58 PM 
Modified:  Feb 24, 2014, 11:14:49 AM → Feb 24, 2014, 11:14:49 AM 
comment:3 Changed 9 years ago by
Authors:  → Ralf Stephan 

Commit:  → c0f4cf53bd33fa88e375a632454a81ce1954a4e1 
Status:  new → needs_review 
comment:4 followup: 5 Changed 9 years ago by
Cc:  Nicolas M. Thiéry added 

Status:  needs_review → needs_work 
While having the category of sequences also being the parent is a definite abuse IMO, I don't like the proposed change since:
 it returns a class rather than an instance, and
 it isn't a container for only finite sequences.
So I would rather see a new class as you propose here with this ticket. Let's do things properly, and the parent shouldn't be too big or complicated either. This parent will also be in the category of Sets
or InfiniteEnumeratedSets
depending on if the base object is enumerable or not.
Also what's the ticket that removes the Sequences
category? I'd almost say do that here as well.
comment:5 Changed 9 years ago by
Replying to tscrim:
So I would rather see a new class as you propose here with this ticket. Let's do things properly, and the parent shouldn't be too big or complicated either. This parent will also be in the category of
Sets
orInfiniteEnumeratedSets
depending on if the base object is enumerable or not.
In my understanding a sequence is always enumerable, it may not be finite, or it may not be mutable. The present class Sequence
is finite and can optionally be immutable so the right category would be FiniteEnumeratedSets
instead of Sets
. I'm not sure if the parent would be a ring as any object can be an element, but I'm no algebraist. Update: I convinced myself it would be a ring, so I propose FiniteSequenceRing
as parent to Sequence
(rename to FiniteSequence
and set Sequence=
it).
Yes the infinite version is desirable but please not in this ticket, too.
Also what's the ticket that removes the
Sequences
category? I'd almost say do that here as well.
#15853 and we have it now so use it.
comment:6 Changed 9 years ago by
A parent in EnumeratedSets
is a set whose elements can be enumerated. So the parent, the set of all sequences, must be enumerable, not the sequences themselves. I'm not convinced of a ring structure, much less a natural one. What is the addition and multiplication operations? I would want addition to be concatenation given the python syntax. I'm not sure at a quick glance that this would give a module structure when the base object has a ring structure (which it may not).
Although since the present class is for finite sequences, I agree that infinite sequences should be done on another ticket.
comment:7 Changed 9 years ago by
Of course you're right, thanks for the explanation. I said I'm no algebraist. I have corrected the ticket description.
comment:8 Changed 9 years ago by
Description:  modified (diff) 

Summary:  make Sequence a FiniteEnumeratedSets → implement Sequence parent from Sets 
comment:9 Changed 9 years ago by
Let's have another attempt at this.
A string (or word) over Σ is any finite sequence of symbols from Σ (which is finite too). The set of all finite strings over some fixed alphabet Σ forms a monoid with string concatenation as the operation. This monoid is denoted Σ∗ and is called the free monoid over Σ. (Taken from Wikipedia)
That this is not far off is seen in combinat/words/word.py
. So it seems that the set of finite sequences over finite sets is a monoid, and this is at least more specialized than a set.
Are there monoids with an infinite number of generators?
comment:10 Changed 9 years ago by
#15289 gives free monoids given by some indexing set. Although I only had enumerable indexing sets in mind, so it may not work over something nonenumerable.
It almost feels like you're going to propose not having a parent for sequences and having them being subsumed by Words
of IndexedFreeMonoid
(if I'm wrong, you can ignore the following). I think we should have a parent for (finite) sequences where we don't include the monoid structure and we think of them as maps from some indexing set to some codomain. Plus I think people will naturally look for Sequences
.
comment:11 Changed 9 years ago by
I am coming completely naive to this, except for my OOP background, and if I can reuse Words
of IndexedFreeMonoid
I would like to. But aren't sequences a very special case that would not benefit from that code?
So to the parent, it looks to me like a subclass of IndexedFreeMonoid
where index_set=ZZ
is hardcoded is just what is needed here.
comment:12 followup: 13 Changed 9 years ago by
The set of all finite (support) sequences is not a free monoid until you put the additional structure of concatenation on it. However we could also give (finite support) sequences the structure of a vector space over k
(thought of as living inside of the infinite direct sum of copies of k
where we surpress trailing zero). The point is the monoid (or what +
means) structure is not canonical, and there is the natural mathematical associations to consider.
If anything, Words/IndexedFreeMonoid
should be a subclass of Sequences
, but I'm not sure this will not come with problems. IMO, it's easier to refactor things together than to separate them out.
comment:13 Changed 9 years ago by
Replying to tscrim:
If anything,
Words/IndexedFreeMonoid
should be a subclass ofSequences
, but I'm not sure this will not come with problems. IMO, it's easier to refactor things together than to separate them out.
So you would call it Sequences
and put it into Sets
?
comment:14 Changed 9 years ago by
I am finally looking at this ticket. Thanks for taking care of long deprecated stuff!
The documentation of Sequence
states «A mutable list of elements with a common guaranteed universe, which can be set immutable».
I interpret that as a data structure for an homogeneous collection of objects, homogeneous in that they share a common universe. This sounds much more like a programming utility than a model for a mathematical concept.
So I would tend to not try imposing a mathematical structure onto it: a sequence needs not have a parent nor a category, nor mathematical operations like +, ... Let's indeed deprecate/remove the corresponding methods.
On the other hand, one could triple check that Sequence
fits nicely in Python's collection Abstract Base Classes [1]. This is a good start:
sage: S = Sequence([QQ, RR]) sage: isinstance(S, collections.MutableSequence) True
There would remain to check that all methods indeed fit the specifications.
[1] https://docs.python.org/2/library/collections.html#collectionsabstractbaseclasses
Cheers,
Nicolas
comment:15 Changed 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:16 Changed 9 years ago by
I don't know about the Python's ABC idea. Do we have a place for classes that fit into that hierarchy?
This ticket grew on me because it forced me to learn a bit about abstract algebra. After all this, I agree that this special class Sequence
has no place in categories/
and that's what the ticket is about, too. However, special subconstructs of the abtract idea of sequence would have a defined place in the category tree, even though a superclass of all these might not. But this is the topic of other possible tickets, and the class Sequence
of this ticket is not such a superclass.
comment:17 followup: 19 Changed 9 years ago by
Description:  modified (diff) 

Summary:  implement Sequence parent from Sets → move Sequence from categories to misc 
comment:18 followup: 20 Changed 9 years ago by
Accompanying this move could be a different name that doesn't surprise the user. While I can find no crisper name than FiniteSequenceWithCommonUniverse
I still think the finiteness should go in and propose it to be FiniteSequence
.
comment:19 Changed 9 years ago by
Hi,
In a recent discussion where we were trying to clarify the role of the various Sage modules, we kind of converged toward the following:
 Sageagnostic data structure > sage.misc  Specific purpose data structure (e.g. graph backend) > sage.graph  Data structure that inherits from, e.g., Element > sage.structure
Here sequence does not inherit from Element/Parent/?..., but it's directly tied to those. So sage.structure
sound like a reasonable spot for Sequence.
comment:20 Changed 9 years ago by
Replying to rws:
Accompanying this move could be a different name that doesn't surprise the user. While I can find no crisper name than
FiniteSequenceWithCommonUniverse
I still think the finiteness should go in and propose it to beFiniteSequence
.
The analog of this in object programming parlance, would be to share a common same class or interface. And such a sequence would be said to be homogeneous. So maybe FiniteHomogeneousSequence
could do (though we don't see that it's homogeneous in the sense of Sage's parents/categories).
comment:21 Changed 9 years ago by
Commit:  c0f4cf53bd33fa88e375a632454a81ce1954a4e1 → 3d1b07b61f7261c6b1c7881ea000467dd9443a2a 

Branch pushed to git repo; I updated commit sha1. New commits:
cb86061  Merge branch 'develop' into t/15852/ticket/15852

719e10c  15852: replace parent() in tests for natural_object() with universe()

b1a35ef  15852: deprecate category() (and with it parent)

3d1b07b  15852: remove category()/parents and dependent imports, doctests

comment:22 Changed 9 years ago by
Description:  modified (diff) 

Status:  needs_work → needs_review 
Summary:  move Sequence from categories to misc → uncouple Sequence from categories 
It appears that deprecating category()/parent()
will pop up warnings in unexpected doctests all over the place, example:
File "src/sage/categories/semigroups.py", line 169, in sage.categories.semigroups.Semigroups.ParentMethods.cayley_graph Failed example: G.show3d(color_by_label=True, edge_size=0.01, edge_size2=0.02, vertex_size=0.03) Expected nothing Got: doctest:757: DeprecationWarning: You possibly can call universe() instead See http://trac.sagemath.org/15852 for details.
Removing both functions silences them. So, unless I'm missing something, removal without deprecation is the only option here.
comment:23 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:24 Changed 8 years ago by
Status:  needs_review → needs_work 

failing doctests, see patchbot reports
comment:25 Changed 8 years ago by
Commit:  3d1b07b61f7261c6b1c7881ea000467dd9443a2a → 7d54af27d168004eea604cdc84ddd2561e6fd6a5 

comment:26 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:27 Changed 8 years ago by
Commit:  7d54af27d168004eea604cdc84ddd2561e6fd6a5 → 174bc75ace96c4e4efa5f6e4f3d70cc4f1e501db 

Branch pushed to git repo; I updated commit sha1. New commits:
174bc75  15852: reverse misplaced patch

comment:28 Changed 8 years ago by
Milestone:  sage6.4 → sage6.6 

Status:  needs_review → needs_work 
branch does not apply
comment:29 Changed 8 years ago by
Commit:  174bc75ace96c4e4efa5f6e4f3d70cc4f1e501db → afb7e92c1bb6e5bc3ace1836f2b28c8a2d698ec1 

Branch pushed to git repo; I updated commit sha1. New commits:
afb7e92  Merge branch 'develop' into t/15852/ticket/15852

comment:30 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:31 Changed 8 years ago by
Status:  needs_review → needs_work 

Two failing doctest, see patchbot report
comment:32 Changed 8 years ago by
Branch:  u/rws/ticket/15852 → u/rws/15852 

comment:33 Changed 8 years ago by
Commit:  afb7e92c1bb6e5bc3ace1836f2b28c8a2d698ec1 → dbadd6a6c65a3700fc9bb4dec6ab8534a5f10d63 

Status:  needs_work → needs_review 
comment:35 Changed 8 years ago by
Commit:  dbadd6a6c65a3700fc9bb4dec6ab8534a5f10d63 → 1f9c338257b8b551acb3038aae7014ad8c2abaa8 

Branch pushed to git repo; I updated commit sha1. New commits:
1f9c338  Merge branch 'develop' into t/15852/15852

comment:36 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:37 Changed 8 years ago by
Reviewers:  → Volker Braun 

Status:  needs_review → positive_review 
Anything that removes that much chaff is a plus ;)
comment:39 Changed 8 years ago by
Branch:  u/rws/15852 → 1f9c338257b8b551acb3038aae7014ad8c2abaa8 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
Trac #15852: cosmetics to remove dependency on category.Sequence
Trac #15852: improve documentation