Meta ticket: unified sequence/lazy list objects

[Ralf Stephan]

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

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

[Matthieu Dien]

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

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

[Matthieu Dien]

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

[Martin Rubey]

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

[Daniel Krenn]

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

[Daniel Krenn]

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?

[Martin Rubey]

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?

[Martin Rubey]

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?

[Daniel Krenn]

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.

[Daniel Krenn]

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

[Martin Rubey]

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?

[Daniel Krenn]

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.

[Martin Rubey]

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

[Daniel Krenn]

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

[Martin Rubey]

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.

[Daniel Krenn]

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

[Daniel Krenn]

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

[Martin Rubey]

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.