lazy_list from various input data #16137

MatthieuDien · 2014-04-11T18:01:01Z

The lazy_list in sage.misc.lazy_list only deals with infinite list built from iterator.
In many situations we want to create infinite list from more various data:

an iterator (current implementation),
an explicit form a function n -> n-th term
an update function: a function that given a buffer of already computed values compute some extra terms (e.g. in the context of words: fixed point of substitutions and in the context of power series: Newton iteration and relaxed multiplication).

Those new lazy lists aim to be very basic Python objects. Their purpose is to be used as fast and reliable data structures in:

words (sage.combinat.words, see also fast (lazy) infinite words #19620)
continued fraction expansions/binary expansions of real numbers
lazy power series (see major improvements to lazy power series #15673)
...

See also: rational o.g.f. #15714, hypergeometric e.g.f. part of #2516

In the original proposal there was also ultimately periodic lazy lists (that would simply store two attributes for the pre-period and period). In this ticket we focus on the ones that need a cache mechanism.

CC: @MatthieuDien @videlec @nthiery @mantepse @rwst

Component: misc

Keywords: LazyPowerSeries, lazy_list, days57

Author: Matthieu Dien, Vincent Delecroix, Daniel Krenn

Branch/Commit: f7960c1

Reviewer: Daniel Krenn

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

The text was updated successfully, but these errors were encountered:

videlec · 2014-04-13T09:31:20Z

comment:3

Hi Ralf,

I think that our third item also includes CFinite sequences. The difference is about how the function update is written. It might be either

def update1(cache):
    cache.append(cache[-1] + cache[-2])

or

def update2(cache):
    return cache[-1]+cache[-2]

Actually, even a closed form is a special case of update1 as one can call len on the cache. Do you agree or did I miss something?

The main task of this ticket is to write precise specifications of what we need... adapting the current implementation of lazy_list is straightforward.

rwst · 2014-04-13T09:56:19Z

comment:4

OK then please clarify the scope of the ticket. Also a periodic list is a special case of update.

mantepse · 2014-04-14T14:58:52Z

comment:5

I don't think it is a good design decision to have lazy_list include functionality that really belong to formal power series or recursive sequences. I think that this is one of the things Axiom/FriCAS really got right: there is one class (in Axiom-parlance: Stream) which does not require any functionality from the elements. Formal power series and sequences then use this class, and allow access to it via a method coefficients.

In any case, there is quite a large interesting hierarchy of formal power series and sequences, and it is in my opinion a very bad idea to single out rational or hypergeometric functions.

Note that I am not at all against functionality that allows to define lazy lists recursively (on the contrary!), just please do not limit it to sequences built of numbers then.

videlec · 2014-04-14T15:16:52Z

comment:6

Replying to @mantepse:

I don't think it is a good design decision to have lazy_list include functionality that really belong to formal power series or recursive sequences. I think that this is one of the things Axiom/FriCAS really got right: there is one class (in Axiom-parlance: Stream) which does not require any functionality from the elements. Formal power series and sequences then use this class, and allow access to it via a method coefficients.

In any case, there is quite a large interesting hierarchy of formal power series and sequences, and it is in my opinion a very bad idea to single out rational or hypergeometric functions.

Note that I am not at all against functionality that allows to define lazy lists recursively (on the contrary!), just please do not limit it to sequences built of numbers then.

Hey Martin,

There is no way lazy_list would be made only of numbers! My first goal was to have better data structure for words (sage.combinat.words). I also had in mind its usage in lazy power series. Do you prefer the new description? Please edit it if there is something wrong. The concrete implementation did not start yet. We are waiting for the best possible specifications...

rwst · 2014-04-14T15:21:04Z

comment:8

I am aware that it looks like we would only look at numbers. But I was only listing what is already available in code. I would like to have an overview of the hierarchy you mention, not the least because it would help with the design of the code planned here. Where could such an overview (of the hierarchy of formal power series and sequences) be found?

videlec · 2014-04-14T15:25:37Z

comment:9

Replying to @rwst:

I am aware that it looks like we would only look at numbers. But I was only listing what is already available in code. I would like to have an overview of the hierarchy you mention, not the least because it would help with the design of the code planned here. Where could such an overview (of the hierarchy of formal power series and sequences) be found?

Ralf,

I do not understand what happened and if you did it on purpose. I modified the description twice and you reverted my changes twice !! It is very annoying.

rwst · 2014-04-14T15:26:49Z

comment:10

What. No way.

videlec · 2014-04-14T15:30:14Z

comment:11

Replying to @rwst:

What. No way.

Yes you did. But, my mistake, only once. Have a look: #16137. It might really be that we were editing the ticket at the same time and something bad happened. I will roll back the previous version.

rwst · 2014-04-14T15:36:32Z

comment:12

Replying to @videlec:

I will roll back the previous version.

Yes, please. Apparently, I opened the 'Modify ticket' form without editing, you saved your change, then (after display of the yellow warning) I saved my comment, and with it the content of the Modify ticket form. Sorry.

videlec · 2014-04-14T15:42:26Z

comment:13

Replying to @rwst:

Replying to @videlec:

I will roll back the previous version.

Yes, please. Apparently, I opened the 'Modify ticket' form without editing, you saved your change, then (after display of the yellow warning) I saved my comment, and with it the content of the Modify ticket form. Sorry.

It is a bit strange that there is no warning that forbid you to add changes from version 6 when 7 is the current one... No problem, the previous version is back.

mantepse · 2014-04-14T16:57:12Z

comment:14

Replying to @rwst:

Where could such an overview (of the hierarchy of formal power series and sequences) be found?

You can find some references in http://arxiv.org/abs/math/0702086. But this is certainly by no means complete.

mantepse · 2014-04-14T17:00:17Z

comment:15

I very much like the new description, nothing to add...

mantepse · 2014-08-13T09:45:34Z

comment:18

Hi there! Is there any news on this front? I'm especially interested because of the connection with #15673...

MatthieuDien · 2014-08-20T08:40:49Z

comment:19

Replying to @mantepse:

Hi there! Is there any news on this front? I'm especially interested because of the connection with #15673...

I should work on it but I did not have much time since the Sage Days :s

I will work on it during September (I hope).

mantepse · 2014-08-20T09:02:31Z

comment:20

Great! No hurry, though...

MatthieuDien · 2014-12-09T17:37:57Z

Branch: u/MatthieuDien/lazy_list_from_various_input_data

MatthieuDien · 2014-12-09T17:56:20Z

comment:22

Hi there !

I propose a draft of code for 'lazy_list_from_iterator' and 'lazy_list_from_fun'.
Currently, the file is composed of three class : one abstract class (but I don't know how to precise this more formally in Python / Cython / Sage) to facorize the code between lazy_list_from_iterator and lazy_list_from_fun.

I have to do choices :

to define lazy list with function I propose to use a fonction which takes 2 arguments : the rank of the element to compute and all the already computed elements
Currently, the _add_ method force the computation of all the elements : that's very annoying for not finite iterator. I suppressed it, for the moment.

Give me feedback !

Thanks

New commits:

`b7a58c2`	`work in progress`
`37e6768`	`work in progress`

dkrenn · 2016-01-14T08:33:16Z

Changed branch from u/vdelecroix/16137 to u/dkrenn/16137

sagetrac-git · 2016-01-14T08:40:51Z

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

`daa9990`	`forgotten change import`

sagetrac-git · 2016-01-14T08:40:51Z

Changed commit from 295a870 to daa9990

vbraun · 2016-01-19T17:46:34Z

comment:115

sage -t --long src/sage/misc/lazy_list.pyx
**********************************************************************
File "src/sage/misc/lazy_list.pyx", line 543, in sage.misc.lazy_list.lazy_list_generic._fit
Failed example:
    l._info()
Expected:
    cache length 0
    start        2
    stop         9223372036854775807
    step         3
Got:
    cache length 0
    start        2
    stop         2147483647
    step         3
**********************************************************************
1 item had failures:
   1 of  10 in sage.misc.lazy_list.lazy_list_generic._fit
    [204 tests, 1 failure, 0.05 s]

videlec · 2016-01-20T19:32:14Z

comment:116

right. 32 bits vs 64 bits. I am fixing the corresponding doctests.

videlec · 2016-01-20T19:43:55Z

Changed commit from daa9990 to 55a1918

videlec · 2016-01-20T19:43:55Z

New commits:

`f1c6036`	`Trac 16137: merge Sage-7.0`
`55a1918`	`Trac 16137: fixing a doctest and a constructor`

videlec · 2016-01-20T19:43:55Z

Changed branch from u/dkrenn/16137 to u/vdelecroix/16137

dkrenn · 2016-01-21T16:44:09Z

comment:118

Replying to @videlec:

right. 32 bits vs 64 bits. I am fixing the corresponding doctests.

As the first number in

stop         9223372036854775807    # 64-bit
stop         2147483648             # 32-bit

2^63-1, I believe that the second should be 2^31-1 = 2147483647. Unfortunately, I don't have a 32-bit system to test.

dkrenn · 2016-01-21T16:46:40Z

comment:119

Replying to @videlec:


f1c6036	`Trac 16137: merge Sage-7.0`

What was the reason for merging? Was there any conflict?
BTW: You did not merge 7.0 into the branch but the other way round, i.e., you merged this ticket into 7.0 (like the release manager). This makes seeing the changes much more difficult, since the git specifications like HEAD^ or HEAD~3 all take the first parent, which now is not the original branch of this ticket anymore.

sagetrac-git · 2016-01-22T01:13:19Z

Changed commit from 55a1918 to f7960c1

sagetrac-git · 2016-01-22T01:13:19Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`f7960c1`	`Trac 16137: fixing a doctest and a constructor`

dkrenn · 2016-02-02T16:13:41Z

comment:121

Replying to @sagetrac-git:

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`f7960c1`	`Trac 16137: fixing a doctest and a constructor`

Sorry for the delay (for some unknown reason I didn't got a notification about the commit; double-checked). Everything is fine now; thanks.

vbraun · 2016-02-02T23:06:40Z

Changed branch from u/vdelecroix/16137 to f7960c1

MatthieuDien added this to the sage-6.2 milestone Apr 11, 2014

MatthieuDien added p: major / 3 labels Apr 11, 2014

This comment has been minimized.

Sign in to view

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014

dkrenn added the s: needs work label Jan 14, 2016

dkrenn added s: positive review and removed s: needs work labels Jan 14, 2016

vbraun added s: needs work and removed s: positive review labels Jan 19, 2016

videlec added s: needs review and removed s: needs work labels Jan 20, 2016

videlec modified the milestones: sage-7.0, sage-7.1 Jan 20, 2016

dkrenn added s: positive review and removed s: needs review labels Feb 2, 2016

vbraun removed the s: positive review label Feb 2, 2016

vbraun closed this as completed in d0078cb Feb 2, 2016

rwst mentioned this issue Dec 29, 2022

Meta ticket: unified sequence/lazy list objects #16107

Open

dkrenn mentioned this issue Dec 29, 2022

extend lazy lists: various improvements and generalizations, new sublists #19895

Open

fchapoton mentioned this issue Dec 23, 2018

remove various deprecated things #26915

Closed

lazy_list from various input data #16137

lazy_list from various input data #16137

Comments

MatthieuDien commented Apr 11, 2014

This comment has been minimized.

videlec commented Apr 13, 2014

This comment has been minimized.

rwst commented Apr 13, 2014

mantepse commented Apr 14, 2014

videlec commented Apr 14, 2014

This comment has been minimized.

This comment has been minimized.

rwst commented Apr 14, 2014

This comment has been minimized.

videlec commented Apr 14, 2014

rwst commented Apr 14, 2014

videlec commented Apr 14, 2014

rwst commented Apr 14, 2014

This comment has been minimized.

videlec commented Apr 14, 2014

mantepse commented Apr 14, 2014

mantepse commented Apr 14, 2014

mantepse commented Aug 13, 2014

MatthieuDien commented Aug 20, 2014

mantepse commented Aug 20, 2014

MatthieuDien commented Dec 9, 2014

MatthieuDien commented Dec 9, 2014

dkrenn commented Jan 14, 2016

sagetrac-git mannequin commented Jan 14, 2016

sagetrac-git mannequin commented Jan 14, 2016

vbraun commented Jan 19, 2016

videlec commented Jan 20, 2016

videlec commented Jan 20, 2016

videlec commented Jan 20, 2016

videlec commented Jan 20, 2016

dkrenn commented Jan 21, 2016

dkrenn commented Jan 21, 2016

sagetrac-git mannequin commented Jan 22, 2016

sagetrac-git mannequin commented Jan 22, 2016

dkrenn commented Feb 2, 2016

vbraun commented Feb 2, 2016