Opened 11 years ago

Closed 10 years ago

Last modified 8 years ago

#12518 closed enhancement (fixed)

Enumerated set from iterator

Reported by: Vincent Delecroix Owned by: Vincent Delecroix
Priority: major Milestone: sage-5.6
Component: combinatorics Keywords: set, iterator
Cc: Štěpán Starosta Merged in: sage-5.6.beta2
Authors: Vincent Delecroix Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12653, #11795, #13778 Stopgaps:

Status badges

Description (last modified by Jeroen Demeyer)

Implementation of a set (using the category framework) from a function that returns an iterator as in

sage: from sage.sets.set_from_iterator import EnumeratedSetFromIterator
sage: E = EnumeratedSetFromIterator(graphs)
{Graph on 0 vertices, Graph on 1 vertex, Graph on 2 vertices, Graph on 2 vertices, Graph on 3 vertices, Graph on 3 vertices, ...}

Note that in order to be able to pickle, we do not build directly a set from an iterator.

A previous implementation in sage-combinat was CombinatorialClassFromIterator? (in sage.combinat.combinat) which is now deprecated.

The patch depends on #12653 which allows to initialize a graph from a dictionnary of iterables.

Apply: trac_12518-enumerated_set_from_iterator-final.patch and trac_12518-enumerated_set_from_iterator-final_fix.patch

Attachments (4)

trac_12518-enumerated_set_from_iterator.patch (34.8 KB) - added by Vincent Delecroix 10 years ago.
trac_12518-enumerated_set_from_iterator-review-ts.patch (10.9 KB) - added by Travis Scrimshaw 10 years ago.
trac_12518-enumerated_set_from_iterator-final.patch (35.1 KB) - added by Vincent Delecroix 10 years ago.
trac_12518-enumerated_set_from_iterator-final_fix.patch (685 bytes) - added by Vincent Delecroix 10 years ago.

Download all attachments as: .zip

Change History (43)

comment:1 Changed 11 years ago by Vincent Delecroix

Hi,

I'm in trouble with two points:

1) What to do with the equality test when the set are both infinite ? (see in the patch the warning printing on stderr)

2) What is the good way to implement the decorator for a method ? The implementation for functions work quite well but in sage.misc.cachefunc the implementation for methods rather than functions seem more tricky.

comment:2 Changed 11 years ago by Štěpán Starosta

Cc: Štěpán Starosta added

comment:3 Changed 11 years ago by Vincent Delecroix

Description: modified (diff)

comment:4 Changed 11 years ago by Vincent Delecroix

Description: modified (diff)
Status: newneeds_review

comment:5 Changed 11 years ago by Vincent Delecroix

I removed trailing whitespaces and correct a failing doctest.

comment:6 Changed 11 years ago by Vincent Delecroix

I changed the attachment in order to make the patchbot happy :-)

comment:7 Changed 11 years ago by David Loeffler

Authors: vdelecroixVincent Delecroix
Reviewers: PatchBot
Status: needs_reviewneeds_work

But patchbot's not happy -- a bunch of doctests fail (as you can see from the latest patchbot logs). I reproduced this by hand on 5.0.beta7, so it's not just a patchbot issue. The failures all have something to do with dicts not being hashable. (I'm not sure what patch has caused this conflict, but it worked in 5.0.beta3; my guess would be #10998.)

comment:8 Changed 11 years ago by Vincent Delecroix

Dependencies: #12653
Description: modified (diff)
Status: needs_workneeds_review

comment:9 Changed 11 years ago by Vincent Delecroix

I just remove the only trailing whitespace (in sage/combinat/combinat.py) that made the patchbot unhappy.

comment:10 Changed 10 years ago by Travis Scrimshaw

Hey Vincent,

I also get the patchbot errors when running the patch in the combinat queue on 5.5.rc0. Also from a quick look-through the patch, there are a few things which I believe needs to be addressed:

  • Documentation and tests for the deprecated functions in combinat/combinat.py
  • An example in iter_with_cache(), I also don't quite understand the documentation.
  • You'll need to add iter_with_cache and set_from_iterator to the documentation by adding/editing a .rst file (probably misc.rst).
  • I prefer to see the reserved words in code blocks: ``None``, ``self``, ``True``, and ``False``
  • Same for input parameters and private functions, even in private functions.
  • I prefer to have as much linking as possible: ex. :class:`EnumeratedSetFromIterator`
  • Instead of
    if x is True:
    ...
    if x is False:
    ...
    
    it is better to do
    if x:
    ...
    if not x:
    ...
    
    in case x is not a boolean (ex. x = 1).

Thanks,
Travis

comment:11 in reply to:  10 ; Changed 10 years ago by Vincent Delecroix

Hi Travis,

I also get the patchbot errors when running the patch in the combinat queue on 5.5.rc0. Also from a quick look-through the patch, there are a few things which I believe needs to be addressed:

  • Documentation and tests for the deprecated functions in combinat/combinat.py

These functions were *only* in the sage-combinat queues and not inside Sage. So the deprecation is just intended for people from combinat who were using it (and I think that none of them uses it).

  • An example in iter_with_cache(), I also don't quite understand the documentation.

I will open (few days) a new ticket for a better implementation of iter_with_cache. There is a similar construction in lazy power series and I would like to merge both. The idea is to have a Python data structure that behave like a list but with possibly infinitely many entries.

  • I prefer to see the reserved words in code blocks: ``None``, ``self``, ``True``, and ``False``

Is there a difference for documentation ? I thought that code blocks open a new paragraph.

Thanks for careful reading, I will adress all remarks in a new patch.

Best, Vincent

comment:12 in reply to:  11 Changed 10 years ago by Travis Scrimshaw

Hey Vincent,

I also get the patchbot errors when running the patch in the combinat queue on 5.5.rc0. Also from a quick look-through the patch, there are a few things which I believe needs to be addressed:

  • Documentation and tests for the deprecated functions in combinat/combinat.py

These functions were *only* in the sage-combinat queues and not inside Sage. So the deprecation is just intended for people from combinat who were using it (and I think that none of them uses it).

Since these functions are not in sage, its probably best to remove these functions from this patch and then put a second patch in the combinat queue deprecating these functions.

  • I prefer to see the reserved words in code blocks: ``None``, ``self``, ``True``, and ``False``

Is there a difference for documentation ? I thought that code blocks open a new paragraph.

I should have called it (inline) code format, and it just changes the format in the output html.

Thanks,
Travis

Changed 10 years ago by Vincent Delecroix

comment:13 Changed 10 years ago by Vincent Delecroix

Dependencies: #12653#12653, #13778

comment:14 Changed 10 years ago by Vincent Delecroix

Hi,

The error in patchbot comes from the lazy import of graphs (which does not support pickling). I modify a little bit the implementation to use the generic framework of lazy list (in #13778). In particular, there is no more iter_with_cache.

Best, Vincent

comment:15 Changed 10 years ago by Travis Scrimshaw

Reviewers: PatchBotTravis Scrimshaw

Hey Vincent,

I'm uploading a review patch which just makes some documentation tweaks. Functionally it looks good.

However I would like those functions in combinat/combinat.py removed since they only exist in your patch (I grep'ed the patches in the queue and only found them in this patch), and I believe we don't need to follow the sage deprecation scheme within the combinat queue (please correct me if I'm wrong). If you're worried about it, I would place the functions in a separate patch.

Thank you,
Travis

Changed 10 years ago by Travis Scrimshaw

comment:16 Changed 10 years ago by Vincent Delecroix

Description: modified (diff)

comment:17 in reply to:  15 Changed 10 years ago by Vincent Delecroix

Hi Travis,

I'm uploading a review patch which just makes some documentation tweaks. Functionally it looks good.

I fold your patch in trac_12518-*-final-*

However I would like those functions in combinat/combinat.py removed since they only exist in your patch (I grep'ed the patches in the queue and only found them in this patch), and I believe we don't need to follow the sage deprecation scheme within the combinat queue (please correct me if I'm wrong). If you're worried about it, I would place the functions in a separate patch.

I removed it and I also delete the decorator on bruhat_succ adn bruhat_pred that was previously on the sage-combinat server.

Thanks, Vincent

comment:18 Changed 10 years ago by Travis Scrimshaw

Hey Vincent,

Thanks. However there's one small mistake (and it's mine in the review patch, sorry) in the class doc for EnumeratedSetFromIterator, it should be .. NOTE::, the space is missing.

Best,
Travis

Edit - Once you do this, feel free to set this to positive review.

For patchbot:

Apply only: trac_12518-enumerated_set_from_iterator-final.patch

Last edited 10 years ago by Travis Scrimshaw (previous) (diff)

comment:19 Changed 10 years ago by Vincent Delecroix

Status: needs_reviewpositive_review

All right... done

comment:20 Changed 10 years ago by Vincent Delecroix

Description: modified (diff)

comment:21 Changed 10 years ago by Vincent Delecroix

apply trac_12518-enumerated_set_from_iterator-final.patch

(for patchbot)

comment:22 Changed 10 years ago by Vincent Delecroix

Status: positive_reviewneeds_work

The following does not work

sage: from sage.sets.set_from_iterator import set_from_method
sage: class A:
...     a = 10
...     @set_from_method
...     def f(self):
...         return xsrange(self.a)
sage: a = A()
sage: a.f()             # works perfectly
{0, 1, 2, 3, 4, ...}
sage: A.f(a)            # does not work at all
Traceback (most recent call last):
...
TypeError: f() takes exactly 1 argument (2 given)

It causes many problems with element classes which are Cython classes.

I am on this. Sorry. Vincent

comment:23 Changed 10 years ago by Vincent Delecroix

apply trac_12518-enumerated_set_from_iterator-final.patch

(for patchbot)

comment:24 Changed 10 years ago by Vincent Delecroix

Status: needs_workneeds_review

comment:25 Changed 10 years ago by Travis Scrimshaw

Hey Vincent,

Could you remove all of your (commented) print statements and move the DummyExampleForPicklingTest into the doctest for __init__() where you use it?

Thanks,
Travis

comment:26 in reply to:  25 ; Changed 10 years ago by Vincent Delecroix

Hey Travis,

Could you remove all of your (commented) print statements

This I can.

and move the DummyExampleForPicklingTest into the doctest for __init__() where you use it?

Do you mean put the whole class DummyExampleForPicklingTest? into the doctest ? If it is the case, I can not because pickling classes defined in an interactive console is not (easily) possible.

Cheers, Vincent

comment:27 in reply to:  26 Changed 10 years ago by Travis Scrimshaw

Replying to vdelecroix:

and move the DummyExampleForPicklingTest into the doctest for __init__() where you use it?

Do you mean put the whole class DummyExampleForPicklingTest? into the doctest ? If it is the case, I can not because pickling classes defined in an interactive console is not (easily) possible.

Ah okay, then a quick doctest for the f() method and something like:

.. WARNING::

    This class is used for pickling tests only. Do not use.

docstring for the class. Thanks.

Changed 10 years ago by Vincent Delecroix

comment:28 Changed 10 years ago by Vincent Delecroix

apply trac_12518-enumerated_set_from_iterator-final.patch

(for patchbot)

comment:29 Changed 10 years ago by Travis Scrimshaw

Status: needs_reviewpositive_review

Looks good to me now. Thanks Vincent.

comment:30 in reply to:  29 Changed 10 years ago by Vincent Delecroix

Replying to tscrim:

Looks good to me now. Thanks Vincent.

Thanks for your review !

comment:31 Changed 10 years ago by Vincent Delecroix

Description: modified (diff)

apply trac_12518-enumerated_set_from_iterator-final.patch trac_12518-enumerated_set_from_iterator-final_fix.patch

(for patchbot)

comment:32 Changed 10 years ago by Jeroen Demeyer

Dependencies: #12653, #13778#12653, #11795, #13778
Milestone: sage-5.6sage-pending

comment:33 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-pendingsage-5.6

comment:34 Changed 10 years ago by Jeroen Demeyer

Description: modified (diff)

comment:35 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

Changed 10 years ago by Vincent Delecroix

comment:36 in reply to:  35 Changed 10 years ago by Vincent Delecroix

Replying to jdemeyer:

trac_12518-enumerated_set_from_iterator-final_fix.patch is missing a commit message.

Thanks. Done.

comment:37 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.6.beta2
Resolution: fixed
Status: needs_workclosed

comment:38 Changed 8 years ago by Jeroen Demeyer

Could you please explain the motivation behind the doctests

        TESTS::

            sage: from sage.sets.set_from_iterator import set_from_method
            sage: from sage.structure.misc import getattr_from_other_class
            sage: class A:
            ...      stop = 10000
            ...      @set_from_method
            ...      def f(self,start):
            ...          return xsrange(start,self.stop)
            sage: a = A()
            sage: getattr_from_other_class(a, A, 'f')(4)
            {4, 5, 6, 7, 8, ...}

            sage: class B:
            ...      stop = 10000
            ...      @set_from_method(category=FiniteEnumeratedSets())
            ...      def f(self,start):
            ...          return xsrange(start,self.stop)
            sage: b = B()
            sage: getattr_from_other_class(b, B, 'f')(2)
            {2, 3, 4, 5, 6, ...}

However, the documentation of getattr_from_other_class says:

    If self is an instance of cls, raises an ``AttributeError``, to
    avoid a double lookup. This function is intended to be called from
    __getattr__, and so should not be called if name is an attribute
    of self.

But this is precisely what that doctest is doing! Due to a bug in getattr_from_other_class (see #17801), the AttributeError is not always raised when it should. The obvious fix for that bug gives doctest failures in the above doctests.

comment:39 in reply to:  38 Changed 8 years ago by Vincent Delecroix

Replying to jdemeyer:

Could you please explain the motivation behind the doctests ...

No idea. I guess it would be safe to replace them with sage: A.f(a,4) and sage: B.f(b,2).

Note: See TracTickets for help on using tickets.