uncouple Sequence from categories

[Ralf Stephan]

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.

[Ralf Stephan]

New commits:

​cee2e59	Trac #15852: cosmetics to remove dependency on category.Sequence
​c0f4cf5	Trac #15852: improve documentation

[Travis Scrimshaw]

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.

[Ralf Stephan]

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 or InfiniteEnumeratedSets 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.

[Travis Scrimshaw]

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.

[Ralf Stephan]

Of course you're right, thanks for the explanation. I said I'm no algebraist. I have corrected the ticket description.

[Ralf Stephan]

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?

[Travis Scrimshaw]

#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.

[Ralf Stephan]

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.

[Travis Scrimshaw]

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.

[Ralf Stephan]

Replying to tscrim:

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.

So you would call it Sequences and put it into Sets?

[Nicolas M. Thiéry]

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

[Ralf Stephan]

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.

[Ralf Stephan]

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.

[Nicolas M. Thiéry]

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.

[Nicolas M. Thiéry]

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 be FiniteSequence.

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).

[git]

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

[Ralf Stephan]

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.

[Frédéric Chapoton]

failing doctests, see patchbot reports

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​67c0373	16898: do not give Sage variables the pre-underscore
​6e2d928	Merge branch 'develop' into t/15852/ticket/15852
​7d54af2	15852: fix doctest failures

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​174bc75

15852: reverse misplaced patch

[Frédéric Chapoton]

branch does not apply

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​afb7e92

Merge branch 'develop' into t/15852/ticket/15852

[Frédéric Chapoton]

Two failing doctest, see patchbot report

[Ralf Stephan]

Squashed it all into one commit.

---

New commits:

​dbadd6a

15852: uncouple Sequence from categories

[Frédéric Chapoton]

branch is red, does not apply

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1f9c338

Merge branch 'develop' into t/15852/15852

[Volker Braun]

Anything that removes that much chaff is a plus ;-)

[Ralf Stephan]

Thanks for the review.