Opened 8 years ago

Closed 8 years ago

#13778 closed enhancement (fixed)

lazy list

Reported by: vdelecroix Owned by: jason
Priority: major Milestone: sage-5.6
Component: misc Keywords: list, iterator
Cc: Merged in: sage-5.6.beta1
Authors: Vincent Delecroix Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11795 Stopgaps:

Status badges

Description (last modified by jdemeyer)

Lazy lists are iterators that behave like list and implement a cache mechanism.

Apply in that order:

Attachments (3)

trac_13778-lazy_list-review-ts.patch (4.6 KB) - added by tscrim 8 years ago.
review patch
trac_13778-lazy_list.patch (23.9 KB) - added by vdelecroix 8 years ago.
trac_13778-lazy_list-documentation-vd.patch (4.0 KB) - added by vdelecroix 8 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 8 years ago by leif

Hmmm, haven't really checked the code, but there are a couple of typos (or grammatical errors) in the documentation (besides "non-negative"), and a few instances of missing mark-up (such as self without double-backquotes).

Wonder on which platform

sage: from sage.misc.lazy_list import lazy_list
sage: P = lazy_list(iter(Primes()))[10::4]
sage: P.info()
cache length 0
start        10
stop         2147483647
...

will fail (i.e., INT_MAX will differ)... ;-)

comment:2 Changed 8 years ago by leif

  • Description modified (diff)

comment:3 Changed 8 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from new to needs_review

Hey Vincent,

I've written a review patch which is mostly docstring changes (I've explicitly put in the stop so it does not depend on INT_MAX), but I've changed the _repr_() by just calculating the number of elements instead of the try-catch blocks. Everything else looks good, so if you agree with the changes, set this to positive review.

Best,
Travis

Last edited 8 years ago by tscrim (previous) (diff)

comment:4 Changed 8 years ago by novoselt

If these lists are immutable, shouldn't they be called tuples in Python?..

comment:5 follow-up: Changed 8 years ago by leif

Still some flaws, like "iteratable". I'd also consistently use "must" (instead of "should") in the exceptions, as well as either (e.g.) "Returns ..." (descriptive) or "Return ..." (imperative form) in the docstrings.

[I'll perhapsTM provide another reviewer patch later, but can't tell yet. Just minor issues anyway, so feel free to set it to "positive review" in case I don't.]

comment:6 in reply to: ↑ 5 Changed 8 years ago by vdelecroix

Replying to leif:

Still some flaws, like "iteratable". I'd also consistently use "must" (instead of "should") in the exceptions, as well as either (e.g.) "Returns ..." (descriptive) or "Return ..." (imperative form) in the docstrings.

[I'll perhapsTM provide another reviewer patch later, but can't tell yet. Just minor issues anyway, so feel free to set it to "positive review" in case I don't.]

Right. I correct the "iteratable", change "should" to "must" and put everything in imperative form.

comment:7 Changed 8 years ago by tscrim

  • Status changed from needs_review to positive_review

Looks good to me.

comment:8 Changed 8 years ago by vdelecroix

  • Status changed from positive_review to needs_work

I am sorry. Using and reusing the code I found a mistake

sage: from sage.misc.lazy_list import lazy_list
sage: lazy_list([0,0]
Traceback (most recent call last):
...
IndexError: lazy list index out of range

The problem comes from the fact that (stop - start) step is not the good formula for the length. We should take the ceil and not the floor.

comment:9 Changed 8 years ago by tscrim

I've reverted the _repr_() back and added the above as a doctest. I didn't like the control flow with asserts, but I understand why it has to be done that way now (and I tested lists of length at most 3 before I made the change). Set it to positive review if the revised patches works for you.

Best,
Travis

comment:10 Changed 8 years ago by vdelecroix

I found a safer way to write _repr_() using an auxilliary _fit() method. I also so add additional doctests into __getitem__() at the very end.

I switch using INT_MAX as a limiting value to PY_SSIZE_T_MAX which is defined in pyport.h (imported in Python.h). It makes more sense (and on my computer its size is larger than INT_MAX).

Best, Vincent

PS (for pachbot):

apply trac_13778-lazy_list.patch

comment:11 Changed 8 years ago by vdelecroix

  • Description modified (diff)

comment:12 Changed 8 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Changed 8 years ago by tscrim

review patch

comment:13 Changed 8 years ago by tscrim

  • Description modified (diff)

Hey Vincent,

I like this implementation much better.

I've added a few tests and tweaked documentation, but I've changed the behavior of list() slightly by not checking if stop was large since I did not like the following behavior:

sage: L = lazy_list([0,1]); L
lazy list [0, 1]
sage: L.list()
Traceback
...
ValueError: stop is too large!!

There definitely is a problem with determining when iterators are infinite throughout sage (for example, vector(RR, QQ) in ticket #13556), however I'd rather have finite lazy lists always have a list() method not raise an exception.

I've also added a check if the input to lazy list is a list or tuple, then it sets stop to the length of the list if stop was not specified.

If you agree with the changes, feel free to set this to positive review.

Best,
Travis


For patchbot:

Apply: trac_13778-lazy_list.patch, trac_13778-lazy_list-review-ts.patch

comment:14 follow-up: Changed 8 years ago by vdelecroix

Hi Travis,

The doctest for .info() fails on my machine and for patchbot (if the test pass on your machine, I guess that we do not have the same PY_SSIZE_T_MAX). So I changed it.

I also add a TODO in the method ._update_cache_up_to(n) which may be enhanced (but I was not able to do it because of my poor knowledge of cython).

Best, Vincent

PS (for patchbot):

apply trac_13778-lazy_list.patch trac_13778-lazy_list-review-ts.patch trac_13778-lazy_list-documentation-vd.patch

comment:15 Changed 8 years ago by vdelecroix

  • Description modified (diff)

comment:16 in reply to: ↑ 14 ; follow-up: Changed 8 years ago by tscrim

  • Status changed from needs_review to positive_review

Replying to vdelecroix:

The doctest for .info() fails on my machine and for patchbot (if the test pass on your machine, I guess that we do not have the same PY_SSIZE_T_MAX). So I changed it.

Seems like it.

I also add a TODO in the method ._update_cache_up_to(n) which may be enhanced (but I was not able to do it because of my poor knowledge of cython).

I trying using the python syntax for catching exceptions, and while things seemed to work fine when running in the interpreter, it caused segfaults when running sage -t. I have no idea how to fix this (nor I could not find how to catch python exceptions in a cdef extension function which is where I suspect the problem was).

Short version: I'm happy with the way things currently are, so I'm setting this to positive review (hopefully for the last time XP).

Thanks,
Travis

comment:17 in reply to: ↑ 16 Changed 8 years ago by vdelecroix

Many thanks for the review and your involvement in the ticket.

Vincent

comment:18 Changed 8 years ago by jdemeyer

  • Description modified (diff)

comment:19 Changed 8 years ago by jdemeyer

  • Dependencies set to #11795
  • Status changed from positive_review to needs_work

Please rebase this to #11795, there is a conflict in doc/en/reference/misc.rst

comment:20 Changed 8 years ago by vdelecroix

Rebased.

apply trac_13778-lazy_list.patch trac_13778-lazy_list-review-ts.patch trac_13778-lazy_list-documentation-vd.patch

comment:21 Changed 8 years ago by tscrim

  • Status changed from needs_work to positive_review

comment:22 Changed 8 years ago by jdemeyer

  • Status changed from positive_review to needs_work

The commit messages of the patches should be cleared up. In particular they should not refer to the filename trac_13778-lazy_list-documentation-vd.patch. And why does trac_13778-lazy_list.patch also refer to the other two patches in the commit message?

comment:23 follow-up: Changed 8 years ago by jdemeyer

* ping *

Changed 8 years ago by vdelecroix

Changed 8 years ago by vdelecroix

comment:24 in reply to: ↑ 23 Changed 8 years ago by vdelecroix

Replying to jdemeyer:

* ping *

My apologies.

comment:25 Changed 8 years ago by vdelecroix

apply trac_13778-lazy_list.patch trac_13778-lazy_list-review-ts.patch trac_13778-lazy_list-documentation-vd.patch

comment:26 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.6.beta1
  • Resolution set to fixed
  • Status changed from needs_work to closed
Note: See TracTickets for help on using tickets.