Opened 5 years ago

Last modified 3 years ago

#16107 new enhancement

Meta ticket: unified sequence/lazy list objects

Reported by: rws Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords: days57, LazyPowerSeries
Cc: MatthieuDien, vdelecroix, nthiery, mantepse Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #15852, #15673, #16137, #18565, #19895, #19896 Stopgaps:

Description (last modified by dkrenn)

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

Change History (32)

comment:1 Changed 5 years ago by MatthieuDien

  • Description modified (diff)

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

comment:2 Changed 5 years ago by MatthieuDien

  • Cc Matthieu DIen added
  • Keywords days57 added

comment:3 Changed 5 years ago by vdelecroix

  • Cc MatthieuDien vdelecroix added; Matthieu DIen removed

comment:4 Changed 5 years ago by MatthieuDien

  • Cc nthiery added

comment:5 Changed 5 years ago by MatthieuDien

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

comment:6 Changed 5 years ago by rws

  • Dependencies changed from #15852, #15673 to #15852, #15673, #16107
  • Description modified (diff)

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 5 years ago by mantepse

  • Dependencies changed from #15852, #15673, #16107 to #15852, #15673, #16137

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

comment:9 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 4 years ago by mantepse

  • Keywords LazyPowerSeries added

comment:11 Changed 4 years ago by mantepse

  • Cc mantepse added

comment:12 Changed 3 years ago by dkrenn

  • Description modified (diff)

comment:13 Changed 3 years ago by dkrenn

  • Description modified (diff)
  • Summary changed from unified sequence/lazy list objects in category tree to unified sequence/lazy list objects

comment:14 Changed 3 years ago by dkrenn

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

comment:15 Changed 3 years ago by dkrenn

  • Summary changed from unified sequence/lazy list objects to Meta ticket: unified sequence/lazy list objects

comment:16 follow-up: Changed 3 years ago by dkrenn

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
  1. 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?

comment:17 follow-up: Changed 3 years ago by 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?

comment:18 in reply to: ↑ 16 ; follow-up: Changed 3 years ago by 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?

comment:19 in reply to: ↑ 18 Changed 3 years ago by dkrenn

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.

comment:20 in reply to: ↑ 17 ; follow-up: Changed 3 years ago by dkrenn

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

comment:21 in reply to: ↑ 20 ; follow-up: Changed 3 years ago by 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?

comment:22 in reply to: ↑ 21 ; follow-up: Changed 3 years ago by dkrenn

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.

comment:23 in reply to: ↑ 22 ; follow-up: Changed 3 years ago by 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!)

comment:24 in reply to: ↑ 23 ; follow-up: Changed 3 years ago by dkrenn

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

comment:25 in reply to: ↑ 24 ; follow-up: Changed 3 years ago by 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?)

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

comment:26 in reply to: ↑ 25 ; follow-up: Changed 3 years ago by dkrenn

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

comment:27 in reply to: ↑ 26 ; follow-up: Changed 3 years ago by dkrenn

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

comment:28 in reply to: ↑ 27 Changed 3 years ago by mantepse

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.

comment:29 Changed 3 years ago by dkrenn

  • Description modified (diff)

comment:30 Changed 3 years ago by dkrenn

  • Description modified (diff)

comment:31 Changed 3 years ago by dkrenn

  • Dependencies changed from #15852, #15673, #16137 to #15852, #15673, #16137, #19895, #19896

comment:32 Changed 3 years ago by dkrenn

  • Dependencies changed from #15852, #15673, #16137, #19895, #19896 to #15852, #15673, #16137, #18565, #19895, #19896
  • Description modified (diff)
Note: See TracTickets for help on using tickets.