Opened 5 years ago

Closed 4 years ago

#15852 closed enhancement (fixed)

uncouple Sequence from categories

Reported by: rws Owned by:
Priority: major Milestone: sage-6.6
Component: categories Keywords:
Cc: nthiery Merged in:
Authors: Ralf Stephan Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: 1f9c338 (Commits) Commit: 1f9c338257b8b551acb3038aae7014ad8c2abaa8
Dependencies: Stopgaps:

Description (last modified by rws)

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 5 years ago by rws

  • Description modified (diff)

comment:2 Changed 5 years ago by rws

  • Branch set to u/rws/ticket/15852
  • Created changed from 02/23/14 17:52:58 to 02/23/14 17:52:58
  • Modified changed from 02/24/14 11:14:49 to 02/24/14 11:14:49

comment:3 Changed 5 years ago by rws

  • Authors set to Ralf Stephan
  • Commit set to c0f4cf53bd33fa88e375a632454a81ce1954a4e1
  • Status changed from new to needs_review

New commits:

cee2e59Trac #15852: cosmetics to remove dependency on category.Sequence
c0f4cf5Trac #15852: improve documentation

comment:4 follow-up: Changed 5 years ago by tscrim

  • Cc nthiery added
  • Status changed from needs_review to 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 in reply to: ↑ 4 Changed 5 years ago by rws

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.

Last edited 5 years ago by rws (previous) (diff)

comment:6 Changed 5 years ago by tscrim

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 5 years ago by rws

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

Last edited 5 years ago by rws (previous) (diff)

comment:8 Changed 5 years ago by rws

  • Description modified (diff)
  • Summary changed from make Sequence a FiniteEnumeratedSets to implement Sequence parent from Sets

comment:9 Changed 5 years ago by rws

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 5 years ago by tscrim

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

Last edited 5 years ago by tscrim (previous) (diff)

comment:11 Changed 5 years ago by rws

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: Changed 5 years ago by tscrim

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 in reply to: ↑ 12 Changed 5 years ago by rws

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?

comment:14 Changed 5 years ago by nthiery

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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:16 Changed 5 years ago by rws

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: Changed 5 years ago by rws

  • Description modified (diff)
  • Summary changed from implement Sequence parent from Sets to move Sequence from categories to misc

comment:18 follow-up: Changed 5 years ago by 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.

comment:19 in reply to: ↑ 17 Changed 5 years ago by nthiery

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 in reply to: ↑ 18 Changed 5 years ago by nthiery

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

comment:21 Changed 5 years ago by git

  • Commit changed from c0f4cf53bd33fa88e375a632454a81ce1954a4e1 to 3d1b07b61f7261c6b1c7881ea000467dd9443a2a

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

cb86061Merge branch 'develop' into t/15852/ticket/15852
719e10c15852: replace parent() in tests for natural_object() with universe()
b1a35ef15852: deprecate category() (and with it parent)
3d1b07b15852: remove category()/parents and dependent imports, doctests

comment:22 Changed 5 years ago by rws

  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Summary changed from move Sequence from categories to misc to 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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:24 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

failing doctests, see patchbot reports

comment:25 Changed 5 years ago by git

  • Commit changed from 3d1b07b61f7261c6b1c7881ea000467dd9443a2a to 7d54af27d168004eea604cdc84ddd2561e6fd6a5

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

67c037316898: do not give Sage variables the pre-underscore
6e2d928Merge branch 'develop' into t/15852/ticket/15852
7d54af215852: fix doctest failures

comment:26 Changed 5 years ago by rws

  • Status changed from needs_work to needs_review

comment:27 Changed 5 years ago by git

  • Commit changed from 7d54af27d168004eea604cdc84ddd2561e6fd6a5 to 174bc75ace96c4e4efa5f6e4f3d70cc4f1e501db

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

174bc7515852: reverse misplaced patch

comment:28 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.6
  • Status changed from needs_review to needs_work

branch does not apply

comment:29 Changed 4 years ago by git

  • Commit changed from 174bc75ace96c4e4efa5f6e4f3d70cc4f1e501db to afb7e92c1bb6e5bc3ace1836f2b28c8a2d698ec1

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

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

comment:30 Changed 4 years ago by rws

  • Status changed from needs_work to needs_review

comment:31 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

Two failing doctest, see patchbot report

comment:32 Changed 4 years ago by rws

  • Branch changed from u/rws/ticket/15852 to u/rws/15852

comment:33 Changed 4 years ago by rws

  • Commit changed from afb7e92c1bb6e5bc3ace1836f2b28c8a2d698ec1 to dbadd6a6c65a3700fc9bb4dec6ab8534a5f10d63
  • Status changed from needs_work to needs_review

Squashed it all into one commit.


New commits:

dbadd6a15852: uncouple Sequence from categories

comment:34 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

branch is red, does not apply

comment:35 Changed 4 years ago by git

  • Commit changed from dbadd6a6c65a3700fc9bb4dec6ab8534a5f10d63 to 1f9c338257b8b551acb3038aae7014ad8c2abaa8

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

1f9c338Merge branch 'develop' into t/15852/15852

comment:36 Changed 4 years ago by rws

  • Status changed from needs_work to needs_review

comment:37 Changed 4 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

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

comment:38 Changed 4 years ago by rws

Thanks for the review.

comment:39 Changed 4 years ago by vbraun

  • Branch changed from u/rws/15852 to 1f9c338257b8b551acb3038aae7014ad8c2abaa8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.