Opened 11 years ago

Closed 10 years ago

# Enumerated set from iterator

Reported by: Owned by: Vincent Delecroix Vincent Delecroix major sage-5.6 combinatorics set, iterator Štěpán Starosta sage-5.6.beta2 Vincent Delecroix Travis Scrimshaw N/A #12653, #11795, #13778

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.

### 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:3 Changed 11 years ago by Vincent Delecroix

Description: modified (diff)

### comment:4 Changed 11 years ago by Vincent Delecroix

Description: modified (diff) new → needs_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: vdelecroix → Vincent Delecroix → PatchBot needs_review → 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 11 years ago by Vincent Delecroix

Dependencies: → #12653 modified (diff) needs_work → needs_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 follow-up:  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`
• 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``
```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:  12 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

### 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 follow-up:  17 Changed 10 years ago by Travis Scrimshaw

Reviewers: PatchBot → 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 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_review → positive_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_review → 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 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_work → needs_review

### comment:25 follow-up:  26 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 ; follow-up:  27 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

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 10 years ago by Vincent Delecroix

apply trac_12518-enumerated_set_from_iterator-final.patch

(for patchbot)

### comment:29 follow-up:  30 Changed 10 years ago by Travis Scrimshaw

Status: needs_review → positive_review

Looks good to me now. Thanks Vincent.

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

Looks good to me now. Thanks Vincent.

### 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 sage-5.6 → sage-pending

### comment:33 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-pending → sage-5.6

### comment:34 Changed 10 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:35 follow-up:  36 Changed 10 years ago by Jeroen Demeyer

Status: positive_review → needs_work

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

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 → fixed needs_work → closed

### comment:38 follow-up:  39 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

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