Opened 8 years ago

Closed 7 years ago

Last modified 5 years ago

#12518 closed enhancement (fixed)

Enumerated set from iterator

Reported by: vdelecroix Owned by: vdelecroix
Priority: major Milestone: sage-5.6
Component: combinatorics Keywords: set, iterator
Cc: sstarosta 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:

Description (last modified by jdemeyer)

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)

Change History (43)

comment:1 Changed 8 years ago by vdelecroix

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 8 years ago by sstarosta

  • Cc sstarosta added

comment:3 Changed 8 years ago by vdelecroix

  • Description modified (diff)

comment:4 Changed 8 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from new to needs_review

comment:5 Changed 8 years ago by vdelecroix

I removed trailing whitespaces and correct a failing doctest.

comment:6 Changed 8 years ago by vdelecroix

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

comment:7 Changed 8 years ago by davidloeffler

  • Authors changed from vdelecroix to Vincent Delecroix
  • Reviewers set to PatchBot
  • Status changed from needs_review to needs_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 8 years ago by vdelecroix

  • Dependencies set to #12653
  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:9 Changed 8 years ago by vdelecroix

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

comment:10 follow-up: Changed 7 years ago by tscrim

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 ; follow-up: Changed 7 years ago by vdelecroix

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 7 years ago by tscrim

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 7 years ago by vdelecroix

comment:13 Changed 7 years ago by vdelecroix

  • Dependencies changed from #12653 to #12653, #13778

comment:14 Changed 7 years ago by vdelecroix

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 follow-up: Changed 7 years ago by tscrim

  • Reviewers changed from PatchBot to Travis 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

comment:16 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:17 in reply to: ↑ 15 Changed 7 years ago by vdelecroix

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 7 years ago by tscrim

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 7 years ago by tscrim (previous) (diff)

comment:19 Changed 7 years ago by vdelecroix

  • Status changed from needs_review to positive_review

All right... done

comment:20 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:21 Changed 7 years ago by vdelecroix

apply trac_12518-enumerated_set_from_iterator-final.patch

(for patchbot)

comment:22 Changed 7 years ago by vdelecroix

  • Status changed from positive_review to needs_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 7 years ago by vdelecroix

apply trac_12518-enumerated_set_from_iterator-final.patch

(for patchbot)

comment:24 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:25 follow-up: Changed 7 years ago by tscrim

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 ; follow-up: Changed 7 years ago by vdelecroix

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 7 years ago by tscrim

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.

comment:28 Changed 7 years ago by vdelecroix

apply trac_12518-enumerated_set_from_iterator-final.patch

(for patchbot)

comment:29 follow-up: Changed 7 years ago by tscrim

  • Status changed from needs_review to positive_review

Looks good to me now. Thanks Vincent.

comment:30 in reply to: ↑ 29 Changed 7 years ago by vdelecroix

Replying to tscrim:

Looks good to me now. Thanks Vincent.

Thanks for your review !

comment:31 Changed 7 years ago by vdelecroix

  • 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 7 years ago by jdemeyer

  • Dependencies changed from #12653, #13778 to #12653, #11795, #13778
  • Milestone changed from sage-5.6 to sage-pending

comment:33 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-pending to sage-5.6

comment:34 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:35 follow-up: Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

comment:36 in reply to: ↑ 35 Changed 7 years ago by vdelecroix

Replying to jdemeyer:

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

Thanks. Done.

comment:37 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.6.beta2
  • Resolution set to fixed
  • Status changed from needs_work to closed

comment:38 follow-up: Changed 5 years ago by jdemeyer

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 5 years ago by vdelecroix

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.