uncouple Sequence from categories

[rwst]

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.

CC: @nthiery

Component: categories

Author: Ralf Stephan

Branch/Commit: 1f9c338

Reviewer: Volker Braun

Issue created by migration from https://trac.sagemath.org/ticket/15852

[rwst]

Branch: u/rws/ticket/15852

[rwst]

Commit: c0f4cf5

[rwst]

Author: Ralf Stephan

[rwst]

New commits:

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

[tscrim]

comment:4

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.

[rwst]

comment:5

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.

[tscrim]

comment:6

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.

[rwst]

comment:7

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

[rwst]

comment:9

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?

[tscrim]

comment:10

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

[rwst]

comment:11

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.

[tscrim]

comment:12

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.

[rwst]

comment:13

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?

[nthiery]

comment:14

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

[rwst]

comment:16

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.

[rwst]

comment:18

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.

[sagetrac-git]

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

afb7e92

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

[sagetrac-git]

Changed commit from 174bc75 to afb7e92

[fchapoton]

comment:31

Two failing doctest, see patchbot report

[rwst]

Changed branch from u/rws/ticket/15852 to u/rws/15852

[rwst]

Changed commit from afb7e92 to dbadd6a

[rwst]

comment:33

Squashed it all into one commit.

---

New commits:

dbadd6a

15852: uncouple Sequence from categories

[fchapoton]

comment:34

branch is red, does not apply

[sagetrac-git]

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

1f9c338

Merge branch 'develop' into t/15852/15852

[sagetrac-git]

Changed commit from dbadd6a to 1f9c338

[vbraun]

comment:37

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

[vbraun]

Reviewer: Volker Braun

[rwst]

comment:38

Thanks for the review.

[vbraun]

Changed branch from u/rws/15852 to 1f9c338