Opened 8 years ago
Closed 7 years ago
#16137 closed enhancement (fixed)
lazy_list from various input data
Reported by: | MatthieuDien | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.1 |
Component: | misc | Keywords: | LazyPowerSeries, lazy_list, days57 |
Cc: | MatthieuDien, vdelecroix, nthiery, mantepse, rws | Merged in: | |
Authors: | Matthieu Dien, Vincent Delecroix, Daniel Krenn | Reviewers: | Daniel Krenn |
Report Upstream: | N/A | Work issues: | |
Branch: | f7960c1 (Commits, GitHub, GitLab) | Commit: | f7960c1038c1498eca8995a3e39e7c3a4f76e99e |
Dependencies: | Stopgaps: |
Description (last modified by )
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 #19620) - continued fraction expansions/binary expansions of real numbers
- lazy power series (see #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.
Change History (122)
comment:1 Changed 8 years ago by
- Cc mantepse added
comment:2 follow-up: ↓ 3 Changed 8 years ago by
- Cc rws added
- Description modified (diff)
comment:3 in reply to: ↑ 2 Changed 8 years ago by
- Description modified (diff)
comment:4 Changed 8 years ago by
OK then please clarify the scope of the ticket. Also a periodic list is a special case of update.
comment:5 follow-ups: ↓ 6 ↓ 8 Changed 8 years ago by
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.
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 15 Changed 8 years ago by
- Description modified (diff)
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 methodcoefficients
.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...
comment:7 Changed 8 years ago by
- Description modified (diff)
comment:8 in reply to: ↑ 5 ; follow-ups: ↓ 9 ↓ 14 Changed 8 years ago by
- Description modified (diff)
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?
comment:9 in reply to: ↑ 8 Changed 8 years ago by
Replying to rws:
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.
comment:10 follow-up: ↓ 11 Changed 8 years ago by
What. No way.
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 8 years ago by
Replying to rws:
What. No way.
Yes you did. But, my mistake, only once. Have a look: http://trac.sagemath.org/ticket/16137?action=diff&version=8. 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.
comment:12 in reply to: ↑ 11 ; follow-up: ↓ 13 Changed 8 years ago by
Replying to vdelecroix:
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.
comment:13 in reply to: ↑ 12 Changed 8 years ago by
- Description modified (diff)
Replying to rws:
Replying to vdelecroix:
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.
comment:14 in reply to: ↑ 8 Changed 8 years ago by
Replying to rws:
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.
comment:15 in reply to: ↑ 6 Changed 8 years ago by
I very much like the new description, nothing to add...
comment:16 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:17 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:18 follow-up: ↓ 19 Changed 8 years ago by
Hi there! Is there any news on this front? I'm especially interested because of the connection with #15673...
comment:19 in reply to: ↑ 18 Changed 8 years ago by
comment:20 Changed 8 years ago by
Great! No hurry, though...
comment:21 Changed 8 years ago by
- Branch set to u/MatthieuDien/lazy_list_from_various_input_data
comment:22 Changed 8 years ago by
- Commit set to 37e67683e7a2f10152ba3a01b8aed508fe92f0f1
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
|
comment:23 Changed 8 years ago by
Comments (IMPORTANT: I have hardly any understanding of python/cython necessities, so some of these may be very naive or stupid)
1.) Concerning the *original* lazy_list
, I would have expected that
sage: from sage.misc.lazy_list import lazy_list sage: l = lazy_list(Primes()) sage: l[:100]
returns a list, not a lazy list. (I'm aware of l[:100].list()
, but this seems inconsistent: l[0]
also returns an element, not a lazy list)
Do you know a reason for this decision? Possibly it's more practical, right?
2.) Concerning the *new* lazy_list
some things clearly don't work:
sage: from sage.misc.lazy_list import lazy_list_from_iterator sage: from itertools import count sage: l2 = lazy_list_from_iterator(count()); l2 lazy list [0, 1, 2, ...] sage: l2[:10] (0, 10, 1) sage: l2[10] --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-8-02ea92939ca1> in <module>() ----> 1 l2[Integer(10)] /home/rubey/sage-lazy_list/local/lib/python2.7/site-packages/sage/misc/lazy_list.so in sage.misc.lazy_list.lazy_list_from_iterator.__getitem__ (build/cythonized/sage/misc/lazy_list.c:6074)() TypeError: 'int' object is not iterable
3.) Yes, I think that lazy_list_from_fun
(besides: I would prefer lazy_list_from_function
) should do precisely as you say. Currently, it doesn't: I would have expected the following to return
a lazy list full of empty lists...
sage: l3 = lazy_list_from_fun(lambda a, b: b); l3 lazy list [[[...], [...], [...], [...]], [[...], [...], [...], [...]], [[...], [...], [...], [...]], ...]
4.) There are now two entry points: lazy_list_from_fun
and lazy_list_from_iterator
. I would expect that in the end there is also a general purpose constructor which decides what to use
depending on the type of the argument, right?
comment:24 follow-up: ↓ 25 Changed 8 years ago by
Hello,
Cool. Thanks Matthieu!
1) Please use complete names lazy_list_from_function
and not abreviations. (see also item 3 of Martin)
2) For your specifications, I really do not think it is the best way to do. Very often you have functions that update *many* values at a time (think about Newton method, or substitutively defined sequences). I would prefer much more lazy_list_from_function
whose argument would be a function f(computed_values)
and which would update the list computed_values
with one iteration of the algorithm (and return nothing or possibly an error code). And it has no sense to send the size of the cache to that function (since it is a list and a list knows its length).
3) I think we need more classes (I am not convinced by all names). Some of them might be implemented in further tickets
lazy_list: abstract class | +-- lazy_list_periodic: ultimately periodic lazy list (attributes=two lists) | +-- lazy_list_explicit: (attribute=function n-> u_n) | +-- lazy_list_concatenation: a concatenation of a finite liste and a lazy list | +-- lazy_list_slice: a slice of another lazy list | +-- lazy_list_with_cache: a cache management | +-- lazy_list_from_iterator: the old lazy_list | +-- lazy_list_from_function: update function (basically what you did)
4) we need a unique entry point for all these classes which must be of course lazy_list
.
5) In the old implementation lazy_list
were immutable. It has the advantage of having shared slices. On the other hand it is annoying because they are immutable and hence it will be forbidden to have operations like "f += 1" without a (light) copy.
Vincent
comment:25 in reply to: ↑ 24 ; follow-up: ↓ 28 Changed 8 years ago by
Replying to vdelecroix:
Cool. Thanks Matthieu!
a second that! Sorry about not having mentioned that earlier!
2) [...] I would prefer much more
lazy_list_from_function
whose argument would be a functionf(computed_values)
and which would update the listcomputed_values
with one iteration of the algorithm (and return nothing or possibly an error code). And it has no sense to send the size of the cache to that function (since it is a list and a list knows its length).
OK, I didn't know that python's lists know their length, so +1
3) I think we need more classes
I think we should try to avoid redundancy. I guess, redundancy will be obvious once coded...
However, I also thought that something like lazy_list_explicit
would be very useful. I'm not sure: is turning on caching for a function in python easy enough so that a cached variant of this would not make sense?
5) In the old implementation
lazy_list
were immutable. It has the advantage of having shared slices. On the other hand it is annoying because they are immutable and hence it will be forbidden to have operations like "f += 1" without a (light) copy.
At least for the applications I have in mind, I think immutability is fine. For example, we will have lazy formal power series, and I certainly do not want to make assignments to those possible. (Think of students who prove to me that exp(z)
equals 2 :-)
Martin
comment:26 Changed 8 years ago by
Another comment: I just killed my sage session by asking for the list of all integers. Is there a possibility to make .list()
interruptable?
Martin
comment:27 Changed 8 years ago by
I do not understand what normalize_slice
does. If I pass an integer, I get that integer plus one. Is this intentional?
comment:28 in reply to: ↑ 25 Changed 8 years ago by
Replying to mantepse:
Replying to vdelecroix:
3) I think we need more classes
I think we should try to avoid redundancy. I guess, redundancy will be obvious once coded...
However, I also thought that something like
lazy_list_explicit
would be very useful. I'm not sure: is turning on caching for a function in python easy enough so that a cached variant of this would not make sense?
yes, but right now only in Sage:
sage: f = lambda n: n*(n+1)/2 sage: f_cached = cached_function(f) sage: f_cached(10) 55 sage: f_cached.get_cache() {((10,), ()): 55}
comment:29 Changed 8 years ago by
- Commit changed from 37e67683e7a2f10152ba3a01b8aed508fe92f0f1 to 46503af91c0fb4b28f0b37b83182055734c6f0d9
comment:30 follow-up: ↓ 31 Changed 8 years ago by
Thanks for the update! lazy_list_from_iterator
seems fine now. Could you nevertheless say what normalize_slice
does?
For lazy_list_from_function
I now get:
sage: from sage.misc.lazy_list import lazy_list_from_function sage: from itertools import count sage: f = lazy_list_from_function(lambda a, b: a) --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) <ipython-input-96-f1659b043f2a> in <module>() ----> 1 f = lazy_list_from_function(lambda a, b: a) /home/rubey/sage-lazy_list/local/lib/python2.7/site-packages/sage/misc/lazy_list.so in sage.misc.lazy_list.lazy_list_from_function.__init__ (build/cythonized/sage/misc/lazy_list.c:6520)() AttributeError: 'sage.misc.lazy_list.lazy_list_from_function' object has no attribute 'fun'
comment:31 in reply to: ↑ 30 ; follow-up: ↓ 32 Changed 8 years ago by
For
lazy_list_from_function
I now get: [...]
OK, that was easy to fix, in the pxd
the class was still named lazy_list_from_fun
. I actually replaced all occurrences of fun
by function
in both files, to obtain uniform coding style.
However, it appears that I cannot push my changes. What should I do?
comment:32 in reply to: ↑ 31 Changed 8 years ago by
Replying to mantepse:
For
lazy_list_from_function
I now get: [...]OK, that was easy to fix, in the
pxd
the class was still namedlazy_list_from_fun
. I actually replaced all occurrences offun
byfunction
in both files, to obtain uniform coding style.However, it appears that I cannot push my changes. What should I do?
What do you mean? One solution is to push to another branch.
Vincent
comment:33 follow-up: ↓ 34 Changed 8 years ago by
Thanks for the hint, I pushed to a new branch public/lazy_list_from_various_input_data
. Could you check whether this worked?
comment:34 in reply to: ↑ 33 Changed 8 years ago by
Replying to mantepse:
Thanks for the hint, I pushed to a new branch
public/lazy_list_from_various_input_data
. Could you check whether this worked?
No. The branch does exist but the last commit is 46503af (i.e. not different from Matthieu's one). Did you forgot to commit your changes? What does git log
tell you?
comment:35 Changed 8 years ago by
Oh no! I thought git push would be enough... Could you check again now, please...
comment:36 Changed 8 years ago by
You can have a look directly there: http://git.sagemath.org/sage.git/log/?h=public/lazy_list_from_various_input_data
and see that there is no other commit beyond 46503af. If after a git log
you do not see your commit on your computer, there is no way that something appear after a push on the remote one.
comment:37 Changed 8 years ago by
It worked! Many thanks for your patience! I should have rtfm :-)
comment:38 Changed 8 years ago by
- Branch changed from u/MatthieuDien/lazy_list_from_various_input_data to public/lazy_list_from_various_input_data
- Commit changed from 46503af91c0fb4b28f0b37b83182055734c6f0d9 to 258eee2b4f14f42c2e7ac65d62e1d7fef66ed2a2
New commits:
258eee2 | replace fun by function
|
comment:39 Changed 8 years ago by
Thanks for your feedback and your help. I have also set the ticket's branch to the public one.
comment:40 Changed 8 years ago by
Great! I'm now going to make function
take one argument only, and I volunteer to clean up the examples there (but probably not right now).
Do you think it's possible to have list comprehensions for lazy_list
? FriCAS allows things like:
[i^2 for i in 1.. | prime? i]
Otherwise, we need at least a function that makes a new lazy_list
by applying a function (lazy_list_explicit
might do) but also a way to select members from a lazy_list
.
comment:41 Changed 8 years ago by
- Commit changed from 258eee2b4f14f42c2e7ac65d62e1d7fef66ed2a2 to 530b21b1a97012b1adfc244dad57250922f4f46c
Branch pushed to git repo; I updated commit sha1. New commits:
530b21b | make function accept only the previous values as argument
|
comment:42 Changed 8 years ago by
Although less elegant, we can do the following:
sage: m = lazy_list_from_function(len); m lazy list [0, 1, 2, ...] sage: m2 = lazy_list_from_iterator(ifilter(is_prime, m)); m2 lazy list [2, 3, 5, ...] sage: m3 = lazy_list_from_iterator(imap(lambda a: a^2, m2)); m3 lazy list [4, 9, 25, ...]
Now I'm not quite sure anymore what the difference between an iterator and a lazy list is precisely. Is it just the caching? How do we want to interact with itertools
?
comment:43 Changed 8 years ago by
From a brief look at itertools
, it seems to me that we should revisit the design decisions. If I understand correctly, itertools
provides all the operations we might want, except caching and therefore also the functionality of lazy_list_from_function
.
Looking at the example in my previous comment, I'm not quite satisfied with the interaction of lazy_list
and itertools
yet. I'm a bit surprised that itertools
provides functions, not methods.
Edit: I just found a long discussion about the design of iterators, https://mail.python.org/pipermail/python-3000/2006-November/004301.html.
comment:44 Changed 8 years ago by
Hi there,
I just checked that, in a very rudimentary way, we can define lazy lists recursively, as follows:
sage: from sage.misc.lazy_list import * sage: from itertools import * sage: l = lazy_list_recursive(cache = [[]]) sage: l.define(imap(lambda a: [1] + a, l)) sage: l[0], l[1], l[2] ([], [1], [1, 1])
I also had to realise that itertools.product
is not particularly intelligent what concerns infinite streams...
I'll take a break now and wait for feedback. In summary, it now seems to me that we want lazy_list
to be
- a model for "infinite lists", i.e., support slicing
- play as well as possible with iterators
- provide functionality that
itertools
cannot provide:next
depending on the previous values- possibly recursive definitions
- what else?
- what else?
In particular, should lazy_list
additionally provide wrappers for the functionality in itertools
? Currently, I don't think so.
comment:45 Changed 8 years ago by
Hi there,
I found the bug that avoid me to connect on Sage trac (I used my phone's connection). So, I copy the message which I sent by email.
@Martin The diference bewteen lazy_list and iterator is not only the caching. There is also the way to compute an element : if you want the nth element of an iterator you have to compute the (n-1) previous ones, for lazy_list (currently the implementation does not do this but it should in close future) the goal is to compute elements only if it obligatory. For example, you don't want to compute all the coeffcients of a serie if at the end, you will only use the odd (or even) part. Concerning recursive definition, we have to allow it but the implementation must not be recursive because recursion is extremly expensive in Python.
@Vincent
To implement this, I need to overload the _fit
method and pass it in "cdef
mode". I just have a question : why, in the iterator's class, do you use update_cache_up_to
and not _fit
?
And finally, to answer to Martin about "what is _normalize_slice
?", _normalize_slice
means nothing it is just a piece of code that I wanted to factorize. In fact I should factorize directly __getitem__
by adding a method which have to create a slice (last line of code __getitem__
).
comment:46 Changed 8 years ago by
Therefore, the answer of Martin :
@Martin The diference bewteen lazy_list and iterator is not only the caching. There is also the way to compute an element : if you want the nth element of an iterator you have to compute the (n-1) previous ones, for lazy_list (currently the implementation does not do this but it should in close future) the goal is to compute elements only if it obligatory.
For example, you don't want to compute all the coeffcients of a serie if at the end, you will only use the odd (or even) part.
Excellent point!
You made me think again about the name - I don't particularly like "lazy_list". Of course, from a math point of view I'd call it "Sequence". However, I just discovered that this is already taken in Sage for something related, although not identical.
I then discovered "Family", which seems the same but a bit more general. In fact, "lazy_list" is a Family having index set natural numbers.
Shouldn't we merge these two concepts, at least in the long run?
Concerning recursive definition, we have to allow it but the implementation must not be recursive because recursion is extremly expensive in Python.
I'm not quite sure what you mean. There is hardly any implementation. I want that definitions like s = f(s), where "s" is a "lazy list" determined by this equation, can be easily typed into sage.
Thus, I think of it as a convenience feature, for rapid prototyping. Its usefulness lies in the fact that it's very general. Thus, from the user's perspective, I wouldn't expect it to do any fancy term-rewriting.
And finally, to answer to Martin about "what is
_normalize_slice
? ",_normalize_slice
means nothing it is just a piece of code that I wanted to factorize. In fact I should factorize directly `getitem ` by adding a method which have to create a slice (last line of code__getitem__
).
OK, thanks!
Best,
Martin
comment:47 follow-up: ↓ 48 Changed 8 years ago by
Should we ask about the desired relationship between Family
, Sequence
and lazy_list
on sage-devel?
comment:48 in reply to: ↑ 47 Changed 8 years ago by
Replying to mantepse:
Should we ask about the desired relationship between
Family
,Sequence
andlazy_list
on sage-devel?
There is already a ticket for that #16107 but we can ask on sage-devel for more feedback.
Concerning Family
, I read documentation and code. That seems cool but not the same goal that lazy_list
, especially concerning the definitions of such objects (Family
can only be defined by iterable objects).
comment:49 Changed 8 years ago by
Thanks for pointing out #16107, I added the LazyPowerSeries
keyword there!
I don't understand your assessment of Family
though, why should it have a different goal? At the very least, lazy_list
should inherit from Family
, no?
comment:50 Changed 8 years ago by
- Commit changed from 530b21b1a97012b1adfc244dad57250922f4f46c to daa5652df3933bf1dc374bfcdfadb4707d0c2723
comment:51 Changed 8 years ago by
- Commit changed from daa5652df3933bf1dc374bfcdfadb4707d0c2723 to d4827065218788bd6990aed6293536a29396fd54
comment:52 Changed 8 years ago by
- Commit changed from d4827065218788bd6990aed6293536a29396fd54 to 9790b69bc62f00af0bb6a2c4d49649ba6a835bd5
Branch pushed to git repo; I updated commit sha1. New commits:
9790b69 | implementation of lazy_list_explicit and its iteratorand some reorganization of the class hierarchy
|
comment:53 Changed 8 years ago by
- Commit changed from 9790b69bc62f00af0bb6a2c4d49649ba6a835bd5 to 19cbfd225f597b50114a0def322f40b3a5a848cd
Branch pushed to git repo; I updated commit sha1. New commits:
19cbfd2 | fix a bug with cached lazy_list
|
comment:54 Changed 8 years ago by
- Commit changed from 19cbfd225f597b50114a0def322f40b3a5a848cd to 6f7cfd949cc0956c0490813a7024cb7a8182324e
Branch pushed to git repo; I updated commit sha1. New commits:
6f7cfd9 | concatenation with list implemented
|
comment:55 Changed 8 years ago by
Hi there,
I implemented almost everyting. I still have to :
- make the factory
- do some factorizations of code
- document and test the code
I think that is the moment to ask you to try this implementation and tell me if there are any problems with the implementations or the design choices.
Best
Matthieu
comment:56 Changed 8 years ago by
Hi Matthieu!
I watched you work :-) THANK YOU!!!
Right now I have only two comments:
1.) I think the naming scheme for the classes should be changed:
a) from_iterator
is fine
b) from_function
is misleading. In fact, in analogy to a) I would expect this class to do precisely what explicit
does. Isn't it precisely recursive
?
c) explicit
should in my opinion be named from_function
d) periodic
is fine
I also would suggest to change stopped
to terminating
or finite
.
2.) I still don't understand the relationship with Family
. I guess it's fine not to consider Sequence
right now, but I think the relationship with Family
should be clarified. As a concrete question: should Family
use lazy_list
for sequences?
comment:57 follow-up: ↓ 58 Changed 8 years ago by
Hi Matthieu,
It would be nice to write documentation in the classes, particularly
- what is the input
- how does it work internally
It would help me to read your code.
Do you really want to keep the start, stop, step
for all classes? I would rather add a class
lazy_list_slice
which does the job.
I do not understand anything to lazy_list_explicit
. Why do you use a cache mechanism for it? Moreover, the following
cdef int update_cache_up_to(self, Py_ssize_t i) except -1: while PyList_GET_SIZE(self.cache) <= i: PyList_Append(self.cache, None)
is definitely useless since you can use the self.cache.extend([None]*length)
which would be much faster.
Are you sure you understand the point of Py_INCREF(object)
? If you call it when you should not, it implies that the object will *never* be garbage collected. The call to this function is generally not needed in Cython file.
Now Cython supports iterator, i.e. you can write
cdef class MyClass(X): def __iter__(self): cdef Py_ssize_t i for i in range(self.x,self.y,self.z): yield self.cache[i]
So I would remove all iterators "XYZ_iterator" and implement directly the methods __iter__
when possible.
If you add the line
include "sage/ext/stdsage.pxi"
at the begining of the file you have access to better then "isinstance" to test the type of an object
PY_TYPE_CHECK(object) PY_TYPE_CHECK_EXACT(object)
I have much more comments. I could also edit directly the file.
Vincent
comment:58 in reply to: ↑ 57 Changed 8 years ago by
Hi there,
Thanks you very much for the answers. I will try to justify some of my choices and answer to some of your new questions.
Replying to vdelecroix:
Hi Matthieu,
It would be nice to write documentation in the classes, particularly
- what is the input
- how does it work internally
It would help me to read your code.
Yes, I have to do this
Do you really want to keep the
start, stop, step
for all classes? I would rather add a class
lazy_list_slice
which does the job.
I agree.
I do not understand anything to
lazy_list_explicit
. Why do you use a cache mechanism for it? Moreover, the followingcdef int update_cache_up_to(self, Py_ssize_t i) except -1: while PyList_GET_SIZE(self.cache) <= i: PyList_Append(self.cache, None)is definitely useless since you can use the
self.cache.extend([None]*length)
which would be much faster.
Thanks for the hint, I did not know extend
.
Concerning the usage of a cache mechanism for lazy_list_explicit
, it is because the computation of a list's cell can be long (for example when you compute the Cauchy's product during a lazy series' multiplication). Then, the cache mechanism allows to compute only one time the value contained in a cell.
Are you sure you understand the point of
Py_INCREF(object)
? If you call it when you should not, it implies that the object will *never* be garbage collected. The call to this function is generally not needed in Cython file.
For this point, I have to check that the value is garbage collected, but without this instruction, the value is garbage collected instantly.
Now Cython supports iterator, i.e. you can write
cdef class MyClass(X): def __iter__(self): cdef Py_ssize_t i for i in range(self.x,self.y,self.z): yield self.cache[i]So I would remove all iterators "XYZ_iterator" and implement directly the methods
__iter__
when possible.
Ok, I did not know this. I will benchmark the both approaches.
If you add the line
include "sage/ext/stdsage.pxi"at the begining of the file you have access to better then "isinstance" to test the type of an object
PY_TYPE_CHECK(object) PY_TYPE_CHECK_EXACT(object)
Thanks for the hint.
I have much more comments. I could also edit directly the file. Vincent
Replying to mantepse:
Hi Matthieu!
I watched you work :-) THANK YOU!!!
Right now I have only two comments:
1.) I think the naming scheme for the classes should be changed:
a) from_iterator is fine b) from_function is misleading. In fact, in analogy to a) I would expect this class to do precisely >what explicit does. Isn't it precisely recursive?
from_function
is recursive yes. Do you have an idea about the name (I am really bad to choose name ..) ?
c) explicit should in my opinion be named from_function d) periodic is fine
I also would suggest to change stopped to terminating or finite.
finite
looks better to me, if Vincent agrees ?
2.) I still don't understand the relationship with Family. I guess it's fine not to consider >Sequence right now, but I think the relationship with Family should be clarified. As a concrete >question: should Family use lazy_list for sequences?
I think that this question deserves a new ticket because it can involve modification of the code in an other part of Sage. We can work on it if you want.
Matthieu
comment:59 Changed 8 years ago by
- Commit changed from 6f7cfd949cc0956c0490813a7024cb7a8182324e to 8457edfb98b43d55d73f949860326f30e67a5bf4
Branch pushed to git repo; I updated commit sha1. New commits:
8457edf | iterators replaced by generators (yield keyword), isinstance changed by PY_TYPE_CHECK in __getitem__
|
comment:60 Changed 8 years ago by
- Commit changed from 8457edfb98b43d55d73f949860326f30e67a5bf4 to 1ac24d5075f1b9060309c4ab02a2bd73a5217d6d
Branch pushed to git repo; I updated commit sha1. New commits:
1ac24d5 | remove 'info' method and rename class lazy_list by abstract_lazy_list
|
comment:61 Changed 8 years ago by
Hi there,
I did some of the proposed changes :
- I removed the iterators and use 'yield' instead
- I changed is_instance by PY_TYPE_CHECK in the getitem method to be faster
- I removed the "info" method
Concerning "lazy_list_slice", I have changed my mind : I think it is not necessary because almost all the code managing (start, stop, step) are in the abstract class and the remaining code is dependant of the different class.
At the end, what do you think about my explanation of why lazy_list_explicit must have a cache ?
Matthieu
PS : Doctests will be coming ;)
comment:62 Changed 7 years ago by
Hi, shouldn't this class go to src/sage/data_structures
?
comment:63 Changed 7 years ago by
What is the plan for/status of this the lazy lists of this ticket? (no progress since 10 month now)
comment:64 Changed 7 years ago by
Although I'd also love to see something like this finally be done (I really miss FriCAS here!), I'm afraid that I'm not able to contribute code here. However, I'm willing to learn, and I'm willing to test.
comment:65 follow-up: ↓ 67 Changed 7 years ago by
Hello,
I don't know what Matthieu is currently doing. Note that I have a similar proposal for infinite words in #19620 (with branch whose tests pass). In that case the underlying data is not a list but a char *
from C. Though, the idea is exactly the same. It would be nice to have the same conventions in both cases.
I can provide an implementation for this ticket based on the architecture #19620. We might see later on whether power series needs some raw C datatype as well. Are you willing to review Daniel?
Vincent
comment:66 Changed 7 years ago by
- Description modified (diff)
Other question: do we want a mutability / immutability flag (slice will share memory only if it is set as immutable)?
comment:67 in reply to: ↑ 65 ; follow-up: ↓ 68 Changed 7 years ago by
Replying to vdelecroix:
I can provide an implementation for this ticket based on the architecture #19620.
Ok, what does this mean exactly? (I.e., do you drop the branch attached to this ticket completely and use your own code (from #19620)? Or simply "merge" this in some way?)
no drop no merge. Simply follow the same architecture. We can figure out later on if it makes sense to have a common base class.
Are you willing to review Daniel?
Yes. Good!
comment:68 in reply to: ↑ 67 Changed 7 years ago by
Replying to dkrenn:
Replying to vdelecroix:
I can provide an implementation for this ticket based on the architecture #19620.
Ok, what does this mean exactly? (I.e., do you drop the branch attached to this ticket completely and use your own code (from #19620)? Or simply "merge" this in some way?)
no drop no merge. Simply follow the same architecture. We can figure out later on if it makes sense to have a common base class.
Ok, looking forward to your code (I've already had some look at the existing code of this ticket (and very briefly at #19620)...and I think I like the direction where it is going...)
comment:69 Changed 7 years ago by
- Branch changed from public/lazy_list_from_various_input_data to vdelecroix/16137
- Commit 1ac24d5075f1b9060309c4ab02a2bd73a5217d6d deleted
- Milestone changed from sage-6.4 to sage-7.0
- Status changed from new to needs_review
You can now create lazy lists from iterator and functions. And it is dead simple to create a new class inheriting from lazy_list_abstract
(there is an example in the documentation).
comment:70 Changed 7 years ago by
- Branch changed from vdelecroix/16137 to u/vdelecroix/16137
- Commit set to 5dac074dc5fce5de34818c30e0564d4c35dc1d42
comment:71 Changed 7 years ago by
- Branch changed from u/vdelecroix/16137 to u/dkrenn/16137
comment:72 follow-up: ↓ 97 Changed 7 years ago by
- Commit changed from 5dac074dc5fce5de34818c30e0564d4c35dc1d42 to 8cee245894c11639eac8a6756ce35170041713df
- Status changed from needs_review to needs_work
I made a couple of smaller/minor changes during review; need cross-review. Additionally the following should be addressed/discussed:
_new_slice
and other private methods:_new_slice_
(underscore at the end as well)?
- description, INPUT/OUTPUT of
lazy_list
is missing
- should
list(cache)
appear in the code so that the cache cannot be changed 8accidentally) from outside since only a reference of the list is passed? This would also allow e.g. tuples as well. Or is it meant thatcache
really specifies the cache itself and not only the cached elements. If so, can we make this clear in the doc somewhere (description oflazy_list
)?
_fit
, last example: looks incomplete
__call__
: write oneline description
update_cache_up_to
everwhere: describe return value
:class:`lazy_list`
appears a couple of times, butlazy_list
is not a class anymore
- note-block in
lazy_list_from_iterator
description should (also) be inlazy_list
cache
in INPUT-blocks: everywhere mention that this is a list (see also above)
__reduce__
: oneline description missing
- ticket-description "a pair of finite lists (pre-period, period)": remove from description and create separate ticket for this issue?
- ticket-description "an update function": this was addressed here, but when I see this correctly with a different interface as in the original code. "a function that given a buffer..." we do not have that here. I am fine with it as it is, but IMHO the description of the ticket does not fit anymore. Should this be a separate ticket as well? Maybe also specifying the old branch there to not forget about it?
Moreover, I've did a partial cherry picking of part of the old code of this ticket: the two iterators are removed and a simple yield
in __iter__
now does the job. I adapted it so that it works. Please cross-review.
PS: What about the authorship of this ticket now? MatthieuDien created the original code, that was cherry-picked by me; I've integrated it here and made the necessary changes. I would include us two in the ticket-author field unless you think the changes were too small... (I this case I don't mind)
New commits:
40851bd | Trac 16137 review: update doc-indices
|
bd68b5a | Trac 16137 review: some smaller changes
|
c30746f | return value of _fit
|
f092fc3 | partial cherr-pick of 8457edf: iterators replaced by generators; make this work
|
8cee245 | Merge branch 'u/dkrenn/16137' into u/vdelecroix/16137
|
comment:73 Changed 7 years ago by
Two more issues:
- Since the code was moved from
sage.misc
tosage.data_structures
, do we need a deprecation?
- Since
lazy_list
s are immutable, wouldn't the namelazy_tuple
be more suitable? To rephrase: Help me understand, what makes it a list and not a tuple?
comment:74 follow-up: ↓ 75 Changed 7 years ago by
Concerning 14., I would vote for lazy_stream
or even just stream
, because of https://en.wikipedia.org/wiki/Stream_(computing). There currently is a class Stream
in the species code, which is really a relatively poor implementation of what the code in this ticket does, and I'm quite eager to replace it.
comment:75 in reply to: ↑ 74 Changed 7 years ago by
Replying to mantepse:
Concerning 14., I would vote for
lazy_stream
or even juststream
, because of https://en.wikipedia.org/wiki/Stream_(computing). There currently is a classStream
in the species code, which is really a relatively poor implementation of what the code in this ticket does, and I'm quite eager to replace it.
stream
sounds good to me (from the definition of stream
from your wiki link, it seems that they are lazy by default, so no need to put that into the name).
comment:76 follow-up: ↓ 77 Changed 7 years ago by
Lazy lists might implement a mutable/immutable protocol in the future. In which case the reference to the Python data structure would be appropriate. And it is better to not change the name twice.
Stream is a technical computer term mostly used for communications. As it is said on wikipedia this notion is related to time: it is a "flux of information". It has the relevant menaing in the language Scheme (which is as far as I know, marginally used among mathematicians). I strongly disaprove its usage here.
Other name like lazy_sequence
are already too mathematical.
Unless you have a strong need (and arguments) to change the name I am opposed to it.
comment:77 in reply to: ↑ 76 Changed 7 years ago by
Replying to vdelecroix:
Lazy lists might implement a mutable/immutable protocol in the future.
Ok, then let's keep the name.
comment:78 Changed 7 years ago by
- Branch changed from u/dkrenn/16137 to u/vdelecroix/16137
- Commit changed from 8cee245894c11639eac8a6756ce35170041713df to f1b8d64889eeface3f2ee18472f18a97e654ae5a
- Status changed from needs_work to needs_review
comment:79 follow-up: ↓ 85 Changed 7 years ago by
Hola Daniel,
Thanks!
Replying to dkrenn:
I made a couple of smaller/minor changes during review; need cross-review. Additionally the following should be addressed/discussed:
_new_slice
and other private methods:_new_slice_
(underscore at the end as well)?
I really don't care. But I do not see why it should be with 2 underscores. For me the double underscore methods are saying "I want to interact with the rest of Sage and cares about coercions". Like _add_
, _cmp_
etc. But it might be a personal feeling.
- description, INPUT/OUTPUT of
lazy_list
is missing
done.
- should
list(cache)
appear in the code so that the cache cannot be changed 8accidentally) from outside since only a reference of the list is passed? This would also allow e.g. tuples as well. Or is it meant thatcache
really specifies the cache itself and not only the cached elements. If so, can we make this clear in the doc somewhere (description oflazy_list
)?
This is a feature you might actually want to use. In the constructors __init__
method we clearly want to use the reference to the same list (I made it clear in the doc). In the factory lazy_list
I am in favour of copying and adapted the code accordingly.
_fit
, last example: looks incomplete
Actually not... I had some non trivial error. This method is subtle as for finite lazy_list
you want to avoid the StopIteration
branch. Though I added a _info()
.
__call__
: write oneline description
done
comment:80 follow-up: ↓ 86 Changed 7 years ago by
update_cache_up_to
everwhere: describe return value
The return value was not meaningful (except for Python error handling). I now specified a 0/1
code return and used it in _fit
.
:class:`lazy_list`
appears a couple of times, butlazy_list
is not a class anymore
done
- note-block in
lazy_list_from_iterator
description should (also) be inlazy_list
I moved around a lot of documentation. Tell me if there is still a problem.
cache
in INPUT-blocks: everywhere mention that this is a list (see also above)
done.
__reduce__
: oneline description missing
What for? A user should not care about it. A developer knows what this function is.
- ticket-description "a pair of finite lists (pre-period, period)": remove from description and create separate ticket for this issue?
I reformulated the ticket description. I think this ticket should focus on the lazy lists with a cache.
comment:81 follow-up: ↓ 87 Changed 7 years ago by
- ticket-description "an update function": this was addressed here, but when I see this correctly with a different interface as in the original code. "a function that given a buffer..." we do not have that here. I am fine with it as it is, but IMHO the description of the ticket does not fit anymore. Should this be a separate ticket as well? Maybe also specifying the old branch there to not forget about it?
Actually you could do it by inheritance and implementing _new_slice
. There you have access to the cache with the method get
. See the Thue-Morse example.
I added 20 lines of code to do it from a function. There is a Thue-Morse bis example which uses this path. But I really find this version artificial. If you have an "update function" you generally need some extra variables that are not necesseraily easily deduced from the length of the list. Moreover it is very fragile (since the update function might modify the begining of the list without notice). What do you think? Should I remove it?
Moreover, I've did a partial cherry picking of part of the old code of this ticket: the two iterators are removed and a simple
yield
in__iter__
now does the job. I adapted it so that it works. Please cross-review.
Great! Thanks. I modified it though. Cython is somehow confused with the range stuff if i
is a Py_ssize_t
. I will investigate this and see if I can fix Cython.
comment:82 follow-up: ↓ 84 Changed 7 years ago by
Curiously trac freezes when I tried to send all messages in one. Well I splitted it in 3.
comment:83 Changed 7 years ago by
- Branch changed from u/vdelecroix/16137 to u/dkrenn/16137
comment:84 in reply to: ↑ 82 Changed 7 years ago by
- Commit changed from f1b8d64889eeface3f2ee18472f18a97e654ae5a to 80aad4d9dbc02333435477173ad98871d40625b8
Replying to vdelecroix:
Curiously trac freezes when I tried to send all messages in one. Well I splitted it in 3.
I also sometimes have this problem and no idea what it is (tried to find out, but failed...)
New commits:
80aad4d | Trac 16137: another reviewer commit
|
comment:85 in reply to: ↑ 79 Changed 7 years ago by
Replying to vdelecroix:
Replying to dkrenn:
_new_slice
and other private methods:_new_slice_
(underscore at the end as well)?I really don't care. But I do not see why it should be with 2 underscores. For me the double underscore methods are saying "I want to interact with the rest of Sage and cares about coercions". Like
_add_
,_cmp_
etc. But it might be a personal feeling.
Ok, then let's keep them as they are.
- should
list(cache)
appear in the code so that the cache cannot be changed 8accidentally) from outside since only a reference of the list is passed? This would also allow e.g. tuples as well. Or is it meant thatcache
really specifies the cache itself and not only the cached elements. If so, can we make this clear in the doc somewhere (description oflazy_list
)?This is a feature you might actually want to use. In the constructors
__init__
method we clearly want to use the reference to the same list (I made it clear in the doc). In the factorylazy_list
I am in favour of copying and adapted the code accordingly.
Good solution.
comment:86 in reply to: ↑ 80 ; follow-up: ↓ 90 Changed 7 years ago by
update_cache_up_to
everwhere: describe return valueThe return value was not meaningful (except for Python error handling). I now specified a
0/1
code return and used it in_fit
.
0/1 vs. False/True: isn't there a bint
or something like that?), in particular, since update_cache_up_to is public. If I would change them...
- note-block in
lazy_list_from_iterator
description should (also) be inlazy_list
I moved around a lot of documentation. Tell me if there is still a problem.
Looks good now.
- ticket-description "a pair of finite lists (pre-period, period)": remove from description and create separate ticket for this issue?
I reformulated the ticket description. I think this ticket should focus on the lazy lists with a cache.
Yes, I think so as well. (I don't see any change in the ticket description)
comment:87 in reply to: ↑ 81 ; follow-up: ↓ 91 Changed 7 years ago by
- ticket-description "an update function": this was addressed here, but when I see this correctly with a different interface as in the original code. "a function that given a buffer..." we do not have that here. I am fine with it as it is, but IMHO the description of the ticket does not fit anymore. Should this be a separate ticket as well? Maybe also specifying the old branch there to not forget about it?
Actually you could do it by inheritance and implementing
_new_slice
. There you have access to the cache with the methodget
. See the Thue-Morse example.I added 20 lines of code to do it from a function. There is a Thue-Morse bis example which uses this path. But I really find this version artificial. If you have an "update function" you generally need some extra variables that are not necesseraily easily deduced from the length of the list. Moreover it is very fragile (since the update function might modify the begining of the list without notice). What do you think? Should I remove it?
Since it is already there now, I would keep it. However, I won't need this feature (at this point), so I don't mind if it is removed.
Moreover, I've did a partial cherry picking of part of the old code of this ticket: the two iterators are removed and a simple
yield
in__iter__
now does the job. I adapted it so that it works. Please cross-review.Great! Thanks. I modified it though. Cython is somehow confused with the range stuff if
i
is aPy_ssize_t
. I will investigate this and see if I can fix Cython.
Ok, thank you.
lazy_list_abstract
vs. for examplelazy_list_generic
: I find it a bit strange to instantiate something with "abstract" in its name.
beginning
vs.inital_values
: I have a slight (but not strong) preference for the latter.
I've also made some minor changes; please cross-review.
comment:88 follow-up: ↓ 92 Changed 7 years ago by
Is there a reason, why slices are not a separate class? Is it a design choice? Or simply because the earlier version did so? (I am trying to extend sublist extraction of lazy lists; that's why it comes to my mind).
comment:89 Changed 7 years ago by
- Description modified (diff)
comment:90 in reply to: ↑ 86 ; follow-up: ↓ 95 Changed 7 years ago by
Replying to dkrenn:
update_cache_up_to
everwhere: describe return valueThe return value was not meaningful (except for Python error handling). I now specified a
0/1
code return and used it in_fit
.0/1 vs. False/True: isn't there a
bint
or something like that?), in particular, since update_cache_up_to is public. If I would change them...
Nope nope. It can be -1
if a Python error occurrs (but you will not see it). We can not use bint
here.
comment:91 in reply to: ↑ 87 Changed 7 years ago by
Replying to dkrenn:
- ticket-description "an update function": this was addressed here, but when I see this correctly with a different interface as in the original code. "a function that given a buffer..." we do not have that here. I am fine with it as it is, but IMHO the description of the ticket does not fit anymore. Should this be a separate ticket as well? Maybe also specifying the old branch there to not forget about it?
Actually you could do it by inheritance and implementing
_new_slice
. There you have access to the cache with the methodget
. See the Thue-Morse example.I added 20 lines of code to do it from a function. There is a Thue-Morse bis example which uses this path. But I really find this version artificial. If you have an "update function" you generally need some extra variables that are not necesseraily easily deduced from the length of the list. Moreover it is very fragile (since the update function might modify the begining of the list without notice). What do you think? Should I remove it?
Since it is already there now, I would keep it. However, I won't need this feature (at this point), so I don't mind if it is removed.
Moreover, I've did a partial cherry picking of part of the old code of this ticket: the two iterators are removed and a simple
yield
in__iter__
now does the job. I adapted it so that it works. Please cross-review.Great! Thanks. I modified it though. Cython is somehow confused with the range stuff if
i
is aPy_ssize_t
. I will investigate this and see if I can fix Cython.Ok, thank you.
lazy_list_abstract
vs. for examplelazy_list_generic
: I find it a bit strange to instantiate something with "abstract" in its name.
Much better. I changed it. I was not a fan of the abstract
as well.
beginning
vs.inital_values
: I have a slight (but not strong) preference for the latter.
Changed as well.
comment:92 in reply to: ↑ 88 ; follow-up: ↓ 96 Changed 7 years ago by
Replying to dkrenn:
Is there a reason, why slices are not a separate class? Is it a design choice? Or simply because the earlier version did so? (I am trying to extend sublist extraction of lazy lists; that's why it comes to my mind).
That is a good design question. I have two reasons:
- avoid implementing twice
__getitem__
andget
- (not supported at the moment) the user might want to inherit from
lazy_list_generic
in such way that slices are also instances of the inherited object. In that case we could not make it a distinct class.
comment:93 Changed 7 years ago by
- Branch changed from u/dkrenn/16137 to u/vdelecroix/16137
- Commit changed from 80aad4d9dbc02333435477173ad98871d40625b8 to 85d99c03e0f03bfa23950cc807f28a467259fbc6
New commits:
85d99c0 | Trac 16137: revision 3
|
comment:94 Changed 7 years ago by
- Branch changed from u/vdelecroix/16137 to u/dkrenn/16137
comment:95 in reply to: ↑ 90 Changed 7 years ago by
- Commit changed from 85d99c03e0f03bfa23950cc807f28a467259fbc6 to 72a212c34c0f2a172b9d7ac95d11f24d254a86c3
Replying to vdelecroix:
0/1 vs. False/True: isn't there a
bint
or something like that?), in particular, since update_cache_up_to is public. If I would change them...Nope nope. It can be
-1
if a Python error occurrs (but you will not see it). We can not usebint
here.
Ok, thank you for the clearification.
New commits:
72a212c | Trac 16137 review: fix ReST and remove unnecessary iter
|
comment:96 in reply to: ↑ 92 Changed 7 years ago by
Replying to vdelecroix:
That is a good design question. I have two reasons:
- avoid implementing twice
__getitem__
andget
- (not supported at the moment) the user might want to inherit from
lazy_list_generic
in such way that slices are also instances of the inherited object. In that case we could not make it a distinct class.
Ok.
comment:97 in reply to: ↑ 72 Changed 7 years ago by
- Reviewers set to Daniel Krenn
LGTM, positive whenever a patchbot confirms no errors.
comment:98 Changed 7 years ago by
Thanks for the careful review.
@Martin: if you start reimplementing streams using lazy list, please put me in cc.
comment:99 Changed 7 years ago by
This is wonderful!
Yes, today I started to recollect what I want to do. I'm not sure whether there is any need for another object "stream". Rather, I think that the next step is a good lazy power series implementation.
The main complication is that it is useful to define power series recursively, as in
sage: sage: L = LazyPowerSeriesRing(QQ) sage: one = L(1) sage: monom = L.gen() sage: s = L() sage: s._name = 's' sage: s.define(one+monom*s*s) sage: [s.coefficient(i) for i in range(6)] [1, 1, 2, 5, 14, 42]
In the current code, this is done by keeping track of the "approximate order" of the power series. Note that there are no initial values provided by the user.
An earlier attempt was done by Mike Hansen in #15673, so I guess it's best to continue discussion there. I also have code (for FriCAS, however) that generalizes this using a different approach, via undetermined coefficients and given initial values.
I guess that I am a terrible python programmer, but I think I can give it a try. I would start with what Mike has written, but first I want to recollect how these recursive definitions worked.
comment:100 Changed 7 years ago by
It is perfectly fine to use lazy_list
recursively. With your example one option is
from sage.data_structures.lazy_list import lazy_list_generic class MySerie(lazy_list_generic): def __init__(self): lazy_list_generic.__init__(self, cache=[1]) self._n = 0 def _new_slice(self): n = self._n self._n += 1 return [sum(self.get(i) * self.get(n-i) for i in range(n+1))]
then
sage: f = MySerie() sage: f[0] 1 sage: f[1] 1 sage: f[2] 2 sage: f[3] 5 sage: f[4] 14 sage: f[5] 42
comment:101 Changed 7 years ago by
Yes, I know. The point is that the current user interface does this automatically, and with quite a natural syntax.
comment:102 follow-ups: ↓ 105 ↓ 106 Changed 7 years ago by
Why is this moved to data_structures
? I don't think that "lazy list" is a data structure. And I don't want data_structures
to become yet another "misc".
comment:103 Changed 7 years ago by
Minor comments:
- insert the standard copyright template.
- remove this ugly commented-out code:
# in types.pxd # bint PyType_Check(object o) # bint PyType_CheckExact(object o) # include "sage/ext/python_iterator.pxi"
- remove the unused
from cpython.object cimport *
- remove the unused
from libc import limits
comment:104 Changed 7 years ago by
- Status changed from needs_review to needs_work
comment:105 in reply to: ↑ 102 Changed 7 years ago by
- Branch changed from u/dkrenn/16137 to u/vdelecroix/16137
- Commit changed from 72a212c34c0f2a172b9d7ac95d11f24d254a86c3 to 429be5821297d6dd542c48a5ce1e2db7b4d2c44c
- Status changed from needs_work to needs_info
Replying to jdemeyer:
Why is this moved to
data_structures
? I don't think that "lazy list" is a data structure. And I don't wantdata_structures
to become yet another "misc".
I don't care. I did it because of comment:62. What is a data structure? Just excluding lazy list will not help me to know what should I found out there.
New commits:
429be58 | Trac 16137: removed import + copyright statement
|
comment:106 in reply to: ↑ 102 ; follow-up: ↓ 107 Changed 7 years ago by
Replying to jdemeyer:
Why is this moved to
data_structures
? I don't think that "lazy list" is a data structure. And I don't wantdata_structures
to become yet another "misc".
I don't know about what the motivation of moving it was, but I disagree that it is *not* a data structure. list
is a data structure for sure, so a variant of it, namely our lazy list, is it as well.
The wikipedia says on "data structure" in its first sentence:
In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently.
That's what we have, haven't we?
Why do you think it is not a data structure?
comment:107 in reply to: ↑ 106 Changed 7 years ago by
Replying to dkrenn:
I don't know about what the motivation of moving it was, but I disagree that it is *not* a data structure.
list
is a data structure for sure, so a variant of it, namely our lazy list, is it as well.
Well, the "variant" adds something, but not in terms of the data structure. I would say that a lazy list is some kind of wrapper of a data structure, not a new data structure.
The wikipedia says on "data structure" in its first sentence:
In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently.
That's what we have, haven't we?
Not really. I wouldn't call a lazy list "a way of organizing data".
It you think it is, then essentially everything in Sage is a data structure.
comment:108 Changed 7 years ago by
Data structures should be very basic low-level things. This "lazy list" is too specific and too much Python to fit that definition in my opinion.
comment:109 Changed 7 years ago by
- Commit changed from 429be5821297d6dd542c48a5ce1e2db7b4d2c44c to 295a870b43132d8c7e5c4f3c086b6280d2781a1f
comment:110 follow-up: ↓ 111 Changed 7 years ago by
- Status changed from needs_info to needs_review
All right. Let it go back into where it was. Nobody should complain about something not being at its place in misc.
comment:111 in reply to: ↑ 110 Changed 7 years ago by
- Status changed from needs_review to needs_work
Replying to vdelecroix:
All right. Let it go back into where it was. Nobody should complain about something not being at its place in misc.
The two index.rst
need to be reverted as well...
comment:112 Changed 7 years ago by
- Branch changed from u/vdelecroix/16137 to u/dkrenn/16137
comment:113 Changed 7 years ago by
- Commit changed from 295a870b43132d8c7e5c4f3c086b6280d2781a1f to daa99905c661d199975c01bf39a98b7bb9b7e2ea
Branch pushed to git repo; I updated commit sha1. New commits:
daa9990 | forgotten change import
|
comment:114 Changed 7 years ago by
- Status changed from needs_work to positive_review
comment:115 Changed 7 years ago by
- Status changed from positive_review to needs_work
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]
comment:116 follow-up: ↓ 118 Changed 7 years ago by
right. 32 bits vs 64 bits. I am fixing the corresponding doctests.
comment:117 follow-up: ↓ 119 Changed 7 years ago by
- Branch changed from u/dkrenn/16137 to u/vdelecroix/16137
- Commit changed from daa99905c661d199975c01bf39a98b7bb9b7e2ea to 55a19187320c8aeca6adfb7b5d98acd3274ae207
- Milestone changed from sage-7.0 to sage-7.1
- Status changed from needs_work to needs_review
comment:118 in reply to: ↑ 116 Changed 7 years ago by
Replying to vdelecroix:
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.
comment:119 in reply to: ↑ 117 Changed 7 years ago by
Replying to vdelecroix:
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.
comment:120 follow-up: ↓ 121 Changed 7 years ago by
- Commit changed from 55a19187320c8aeca6adfb7b5d98acd3274ae207 to f7960c1038c1498eca8995a3e39e7c3a4f76e99e
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
|
comment:121 in reply to: ↑ 120 Changed 7 years ago by
- Status changed from needs_review to positive_review
comment:122 Changed 7 years ago by
- Branch changed from u/vdelecroix/16137 to f7960c1038c1498eca8995a3e39e7c3a4f76e99e
- Resolution set to fixed
- Status changed from positive_review to closed
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 eitheror
Actually, even a closed form is a special case of
update1
as one can calllen
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.