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: | sage-6.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 follow-up: 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 non-enumerable.
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 follow-up: 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#collections-abstract-base-classes
Cheers,
Nicolas
comment:15 Changed 9 years ago by
Milestone: | sage-6.2 → sage-6.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 follow-up: 19 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Summary: | implement Sequence parent from Sets → move Sequence from categories to misc |
comment:18 follow-up: 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:
- Sage-agnostic 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: | sage-6.3 → sage-6.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: | sage-6.4 → sage-6.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