Listing infinite sets using never-ending iterators

[Rob Beezer]

Symptom: The following code would appear to run forever, since the
rationals define an iterator that never quits.

QQ.list()

I discovered this when I presumed that

(QQ^2).list()

would raise an error. It doesn't. So I patched the free module code
so the iterator producing module elements would raise an error for a
module over an infinite base ring. That very nearly passed all tests,
except it ran afoul of the category test suite. A doctest for sets
(in the Set_object_union class) constructs a vector space. To get a
generic element for testing the test suite would appear to build an
iterator and then grab the first element produced, so my fix broke
that. (This appears to be at
categories.enumerated_sets._an_element_from_iterator)

It looks like structure.parent._list_from_iterator_cached is where
the first examples get stuck, at least that looks like the right place
when you read the code and that's part of the traceback when you use
ctrl-C.

Options:

1. _list_from_iterator_cached could ask if self is infinite and if
so, fail. This would break the test suite too, I think.

2. The test suite framework needs to get an element by some other
process. For example, (QQ^2).an_element() did not break with my
patch.

3. Tough. You ought to check if a set is infinite before you try to
list it (and students should just learn to do that).

4. Something else.

I've attached one failure of the test suite from my patch to the
module code, there were four very similar failures from the one test:
_test_an_element, _test_elements, _test_elements_eq,
_test_some_elements. The last error message is from my patch.

I'd started this as: http://trac.sagemath.org/sage_trac/ticket/10470

I would prefer to have modules raise an error rather than just hang.
If desired, I can try to fix more fundamental situations, like
ZZ.list(). Comments and suggestions appreciated.

Rob

~~~~~~~~~~~~
File "/sage/dev/devel/sage/sage/sets/set.py", line 864:
sage: TestSuite(X).run()
Expected nothing
Got:
Failure in _test_an_element:
Traceback (most recent call last):
File "/sage/dev/local/lib/python/site-packages/sage/misc/
sage_unittest.py", line 275, in run
test_method(tester = tester)
File "/sage/dev/local/lib/python/site-packages/sage/categories/
sets_cat.py", line 353, in _test_an_element
an_element = self.an_element()
File "/sage/dev/local/lib/python/site-packages/sage/misc/
cachefunc.py", line 322, in __call__
return self._cachedmethod._instance_call(self._instance,
*args, **kwds)
File "/sage/dev/local/lib/python/site-packages/sage/misc/
cachefunc.py", line 466, in _instance_call
cache[key] = self._cachedfunc.f(inst, *args, **kwds)
File "/sage/dev/local/lib/python/site-packages/sage/categories/
enumerated_sets.py", line 441, in _an_element_from_iterator
return it.next()
File "/sage/dev/local/lib/python/site-packages/sage/sets/
set.py", line 939, in __iter__
for x in self.__X:
File "/sage/dev/local/lib/python/site-packages/sage/modules/
free_module.py", line 1046, in __iter__
raise ValueError("module's base ring, or vector space's field,
is not finite, so cannot iterate over elements")
ValueError: module's base ring, or vector space's field, is not
finite, so cannot iterate over elements

[Robert Bradshaw]

I would strongly object to removing the ability to iterate over
infinite sets, sometimes it's very useful to iterate until something
is found, or to grab a certain number of elements. I would be OK with
ZZ.list() throwing an exception as long as "for x in ZZ" still worked
just fine.

- Robert

[Simon King]

On 15 Dez., 01:55, Robert Bradshaw <rober...@math.washington.edu>
wrote:

> I would strongly object to removing the ability to iterate over
> infinite sets, sometimes it's very useful to iterate until something
> is found, or to grab a certain number of elements.

+1

[David Roe]

+1

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

[leif]

On 15 Dez., 01:55, Robert Bradshaw <rober...@math.washington.edu>
wrote:

> I would strongly object to removing the ability to iterate over
> infinite sets, sometimes it's very useful to iterate until something
> is found, or to grab a certain number of elements. I would be OK with
> ZZ.list() throwing an exception as long as "for x in ZZ" still worked
> just fine.

+1

There's a slight difference between infinite and [non-]enumerable sets
you know... ;-)

What about requiring a 'count' parameter to .list() if [we know that]
the set is not finite?


-Leif

[Rob Beezer]

On Dec 15, 3:17 am, leif <not.rea...@online.de> wrote:
> +1
>
> There's a slight difference between infinite and [non-]enumerable sets
> you know...  ;-)

Right. ;-) What I would like to prevent is a hang when naively
asking for the *entire* list of elements of an infinite set, without
having to know (or investigate beforehand) that the set is infinite.
I understand the desire and need for iterators for these sets, as
Robert described. Despite appearances, I wasn't proposing killing
that behavior.

A quick experiment would indicate that checking if a set knows it is
infinite early in _list_from_iterator_cached will prevent most
simple/obvious cases of these hangs without breaking anything else.
I'll put up a real patch for consideration soon.

> What about requiring a 'count' parameter to .list() if [we know that]
> the set is not finite?

I'd think that If someone wants a handful of elements from a set they
know is infinite, then they should construct the iterator (which the
list-building routine is using anyway) and just get their elements
from that? A count keyword would be useful, though then the caching
behavior of these lists might need to be refined.

Rob

[leif]

On 15 Dez., 17:30, Rob Beezer <goo...@beezer.cotse.net> wrote:
> I'd think that If someone wants a handful of elements from a set they
> know is infinite, then they should construct the iterator (which the
> list-building routine is using anyway) and just get their elements
> from that?  A count keyword would be useful, though then the caching
> behavior of these lists might need to be refined.

I thought .list(count=12) or whatever would be more convenient.

Without looking at the code, I suppose making that work with caching
shouldn't be a problem.


-Leif

[Rob Beezer]

On Dec 15, 12:18 pm, leif <not.rea...@online.de> wrote:
> I thought .list(count=12) or whatever would be more convenient.

Yes, that might be a nice enhancement for *somebody* to add, but it
won't solve *my* problem (he says, while scratching an itch). ;-)

> Without looking at the code, I suppose making that work with caching
> shouldn't be a problem.

No it shouldn't be too hard, probably just need to make the count part
of what is cached, or check the length of the cached list against the
count argument.

Rob

[Nicolas M. Thiery]

Hi Rob!

The list method from InfiniteEnumeratedSets() does just that. So here
is a possible route:

- There should be an InfiniteSets() category
- QQ should be in this category
- The list method from InfiniteEnumeratedSets() should be lifted to InfiniteSets()

Shorter alternative: QQ could be in InfiniteEnumeratedSets(). But for
which one of the possible enumerations?

For the record, I am planning to work in the coming month(s?) on
improving the category framework to support "variants" (see [1]); this
should include InfiniteSets as a side product.

Cheers,
Nicolas

[1] http://trac.sagemath.org/sage_trac/wiki/CategoriesRoadMap
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Rob Beezer]

There is now a patch for this at:

http://trac.sagemath.org/sage_trac/ticket/10470

On Dec 22 2010, 2:09 pm, "Nicolas M. Thiery" <Nicolas.Thi...@u-

> Nicolas M. Thi ry "Isil" <nthi...@users.sf.net>http://Nicolas.Thiery.name/