Does itertools.product evaluate its arguments lazily?

Posted on

Question :

Does itertools.product evaluate its arguments lazily?

The following never prints anything in Python 3.6

from itertools import product, count

for f in product(count(), [1,2]): 

Instead, it just sits there and burns CPU. The issue seems to be that product never returns an iterator if it’s over an infinite space because it evaluates the full product first. This is surprising given that the product is supposed to be a generator.

I would have expected this to start counting up (to infinity), something like the behavior of this generator (taken directly from the docs):

for tup in ((x,y) for x in count() for y in [1,2]):

But whereas my generator starts counting immediately, the one using product never counts at all.

Other tools in itertools do what I’d expect. For example, the following:

for f in takewhile(lambda x: True, count()): 

will print a stream of numbers because takewhile is lazy.

Asked By: Shep


Answer #1:

itertools.product generates its results lazily, but this is not true for the arguments. They are evaluated eagerly. Each iterable argument is first converted to a tuple:

The evaluation of the arguments (not the production of results) is very similar to the Python implementation shown in the docs:

pools = [tuple(pool) for pool in args] * repeat

Whereas, in the CPython implementation, pools is a tuple of tuples:

for (i=0; i < nargs ; ++i) {
     PyObject *item = PyTuple_GET_ITEM(args, i);
     PyObject *pool = PySequence_Tuple(item);   /* here */
     if (pool == NULL)
         goto error;
     PyTuple_SET_ITEM(pools, i, pool);
     indices[i] = 0;

This is so since product sometimes needs to go over an iterable more than once, which is not possible if the arguments were left as iterators that can only be consumed once.

You practically cannot build a tuple from an itertools.count object. Consider slicing to a reasonable length with itertools.islice before passing to product.

Answered By: Moses Koledoye

Answer #2:

The issue seems to be that product never returns an iterator

No, product is already “lazy”.

The issue is thatcount() counts to infinity.
From count‘s docs:

Equivalent to:

def count(start=0, step=1):
    # count(10) --> 10 11 12 13 14 ...
    # count(2.5, 0.5) -> 2.5 3.0 3.5 ...
    n = start
    while True:
        yield n
        n += step

You code is basically the same as doing:

def count():
    i = 0
    while True:
        yield i
        i += 1

Answered By: DeepSpace

Answer #3:

I found that

for tup in ((x,y) for x in count() for y in [1,2]):

does what I expect. This is odd given that it is listed as equivelent in the docs. This seems like a bug in itertools.product, but it seems unlikely given how standard it is.

Answered By: Shep

Leave a Reply

Your email address will not be published. Required fields are marked *