Meta ticket: unified sequence/lazy list objects

[rwst]

Several (maybe specialized) implementations of lazy lists exist. This meta ticket can be considered closed when

• uncouple Sequence from categories #15852: uncouple sequence from categories (was earlier: the class Sequence has a parent from the category Sets implemented)
• class Sequence: maybe renaming to FiniteSequence
• lazy_list from various input data #16137: extend lazy_list: lazy_list from various input data
• extend lazy lists: various improvements and generalizations, new sublists #19895: extend lazy_list: various improvements and generalizations, new sublists
• (infinite) homogenous sequences #19896: implementation of class InfiniteSequence
• let both (class Sequence, class InfiniteSequence) use sage.misc.lazy_list
• catalog of sequences in SageMath #18565: catalog of sequences
• major improvements to lazy power series #15673: refactor code in combinat.species.*stream to use sage.misc.lazy_list
• if obsolete close formal/lazy/infinite powerseries #6800

Depends on #15852
Depends on #15673
Depends on #16137
Depends on #18565
Depends on #19895
Depends on #19896

CC: @MatthieuDien @videlec @nthiery @mantepse

Component: combinatorics

Keywords: days57, LazyPowerSeries

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

[MatthieuDien]

comment:1

Fot the last point : I did a benchmark between it and the current implementation and [ticket:6800 #6800] was really slow (and have some bugs).

For now, I have to do a benchmark between [ticket:15673 #15673] and another implementation, so I willl look for look for other points

[MatthieuDien]

Changed keywords from none to days57

[MatthieuDien]

comment:5

After some tests, sage.misc.lazy_list seems to be faster than sage.structure.sequence and sage.combinat.species.*stream because it it cythonized.

We will try to do an implementation of sage.combinat.species.series_stream over sage.misc.lazy_list

[rwst]

Changed dependencies from #15852, #15673 to #15852, #15673, #16107

[mantepse]

Changed dependencies from #15852, #15673, #16107 to #15852, #15673, #16137

[mantepse]

comment:8

I think you meant to add #16137, since #16107 is this ticket.

[mantepse]

Changed keywords from days57 to days57, LazyPowerSeries

[dkrenn]

comment:14

I've updated the description. Please add here what else should be done; maybe something in words? ...or for lazy power series?

[dkrenn]

comment:16

I am thinking about implementing InfiniteSequences and have the following design issue with the two possibilites (it is not restricted to the infinite sequences, but is similar for other classes like words, stream in the species, etc., as well):

1. make lazy_list_generic a base class of InfiniteSequence

2. make an attribute values (or similar) in the class InfiniteSequence which will be an instance of lazy_list_generic

Both have advantages and disadvantages:

• Sequence uses list as a base class, thus InfiniteSequence should use lazy_list
• With 1. you can only use lazy_list_generic, but no derived class like lazy_list_iterator directly; you have to create a lazy_list_generic which tracks the other (as its master attribute; is already implemented since used with slices)
• With 2. you need to write methods for all the things you like from the lazy lists (like building slices etc.). And even then, it is not a lazy list, but just behaves like one.

What do you think?

[mantepse]

comment:17

I just realized that sage.combinat.species.series_stream actually implements streams of coefficients of lazy power series. I'll have to experiment there, too,...

Should InfiniteSequence be the same? What is the algebraic structure?

[mantepse]

comment:18

Replying to @dkrenn:

• With 1. you can only use lazy_list_generic, but no derived class like lazy_list_iterator directly; you have to create a lazy_list_generic which tracks the other (as its master attribute; is already implemented since used with slices)

Could you explain? What does it mean that you cannot use a derived class directly?

[dkrenn]

comment:19

Replying to @mantepse:

Replying to @dkrenn:

• With 1. you can only use lazy_list_generic, but no derived class like lazy_list_iterator directly; you have to create a lazy_list_generic which tracks the other (as its master attribute; is already implemented since used with slices)

Could you explain? What does it mean that you cannot use a derived class directly?

class InfiniteSequence(SageObject, lazy_list_generic)

But when using the factory lazy_list, I may get a lazy_list_iterator or similar, so AFAIK I cannot use it in InfiniteSequence directly. I need to do either

• create class InfiniteSequenceIterator(InfiniteSequence, lazy_list_iterator) (and have to do this for all possible lazy_list_* or
• create a lazy_list_generic (InfiniteSequence), which uses the data of the lazy_list_iterator, i.e., tracks lazy_list_iterator. Thus having always two lazy_list_* instances instantiated.

[dkrenn]

comment:20

Replying to @mantepse:

I just realized that sage.combinat.species.series_stream actually implements streams of coefficients of lazy power series. I'll have to experiment there, too,...

Should InfiniteSequence be the same? What is the algebraic structure?

No algebraic strcture (due to the discussion on #15852 about (finite) sequences).

[mantepse]

comment:21

Replying to @dkrenn:

Replying to @mantepse:

Should InfiniteSequence be the same? What is the algebraic structure?

No algebraic strcture (due to the discussion on #15852 about (finite) sequences).

Ah, but then what is the difference between lazy_list and InfiniteSequence?

[dkrenn]

comment:22

Replying to @mantepse:

Replying to @dkrenn:

Replying to @mantepse:

Should InfiniteSequence be the same? What is the algebraic structure?

No algebraic strcture (due to the discussion on #15852 about (finite) sequences).

Ah, but then what is the difference between lazy_list and InfiniteSequence?

Sequences have a common universe for all the elements of the lazy list and they are (in contrast to lazy list) a SageObject and not only Python's object.

[mantepse]

comment:23

Replying to @dkrenn:

Ah, but then what is the difference between lazy_list and InfiniteSequence?

Sequences have a common universe for all the elements of the lazy list and they are (in contrast to lazy list) a SageObject and not only Python's object.

OK, so in particular this answers my question: a stream of coefficients should not inherit from lazy_list_generic :-) (and thanks for pointing out that lazy_list is not a class!)

[dkrenn]

comment:24

Replying to @mantepse:

Replying to @dkrenn:

Ah, but then what is the difference between lazy_list and InfiniteSequence?

Sequences have a common universe for all the elements of the lazy list and they are (in contrast to lazy list) a SageObject and not only Python's object.

OK, so in particular this answers my question: a stream of coefficients should not inherit from lazy_list_generic :-) (and thanks for pointing out that lazy_list is not a class!)

So your question back to you: What characterizes a stream on your sense?
And why not using lazy_list_generic as base? (To point this out: It works; has advantages and disadvantages).

[mantepse]

comment:25

Sequences have a common universe for all the elements of the lazy list and they are (in contrast to lazy list) a SageObject and not only Python's object.

OK, so in particular this answers my question: a stream of coefficients should not inherit from lazy_list_generic :-) (and thanks for pointing out that lazy_list is not a class!)

So your question back to you: What characterizes a stream on your sense?
And why not using lazy_list_generic as base? (To point this out: It works; has advantages and disadvantages).

(I assume you mean stream of coefficients?)

I want both a common universe and an algebraic structure: all coefficients are from a ring - in particular, I absolutely need a (recognisable!) zero.

[dkrenn]

comment:26

Replying to @mantepse:

Sequences have a common universe for all the elements of the lazy list and they are (in contrast to lazy list) a SageObject and not only Python's object.

OK, so in particular this answers my question: a stream of coefficients should not inherit from lazy_list_generic :-) (and thanks for pointing out that lazy_list is not a class!)

So your question back to you: What characterizes a stream on your sense?
And why not using lazy_list_generic as base? (To point this out: It works; has advantages and disadvantages).

(I assume you mean stream of coefficients?)

Yes.

I want both a common universe and an algebraic structure: all coefficients are from a ring - in particular, I absolutely need a (recognisable!) zero.

What operations are allowed on streams then? (I assume point-wise addition; what do you need multiplication for?)

[dkrenn]

comment:27

Replying to @mantepse:

I want both a common universe and an algebraic structure: all coefficients are from a ring - in particular, I absolutely need a (recognisable!) zero.

So your streams seem to be a more specialized than my sequences. In this way, would it be an option for you that streams have sequences as a base class?
Is a stream of you a Sage Element? (I would guess so).

[mantepse]

comment:28

What operations are allowed on streams then? (I assume point-wise addition; what do you need multiplication for?)

Well, I really want to keep them relatively general, mainly because I won't gain anything by requiring certain operation. I do think that it makes sense to require that the coefficients are from a (possibly noncommutative) ring. I can't think of any applications where we do not have this. I need the recognisable zero to be able to do the trick with recursive definition.

So your streams seem to be a more specialized than my sequences. In this way, would it be an option for you that streams have sequences as a base class?

Yes, certainly.

Is a stream of you a Sage Element? (I would guess so).

Yes.

[dkrenn]

Changed dependencies from #15852, #15673, #16137 to #15852, #15673, #16137, #19895, #19896

[dkrenn]

Changed dependencies from #15852, #15673, #16137, #19895, #19896 to #15852, #15673, #16137, #18565, #19895, #19896