itertools product(infinite iterator) hangs

[Oscar Benjamin]

On Sat, 14 Sep 2019 at 03:26, Oscar Benjamin <oscar.j.benjamin at gmail.com> wrote:
>
> I've been staring at this for a little while:
>
> from itertools import product
>
> class Naturals:
>     def __iter__(self):
>         i = 1
>         while True:
>             yield i
>             i += 1
>
> N = Naturals()
> print(iter(N))
> print(product(N))  # <--- hangs
>
> When I run the above the call to product hangs but I can't see why.

There is already an issue for this:
https://bugs.python.org/issue10109
It seems product always consumes all of its iterators entirely before
yielding anything (in fact before even iter is called). That seemed
surprising to me when looking at the trivial case of a product of one
iterable since in *that* case it is clearly unnecessary.

I wrote my own versions that get around this. This is a simple version:

def iproduct_simple(*iterables):
    '''Returns the Cartesian product of iterables but doesn't hang for
    infinite iterators'''
    if len(iterables) == 0:
        yield ()
        return
    first, others = iterables[0], iterables[1:]
    for f in first:
        for o in iprod(*others):
            yield (f,) + o

This gives output in normal order for finite inputs and doesn't hang
in the case of infinite inputs. However if any of the inputs is
infinite iproduct_simple won't actually yield all elements.

So I made a more complicated version that yields all possibilities
(analogous to enumerating rational numbers):

def iproduct(*iterables):
    '''Returns Cartesian product of iterables. Yields every element
    eventually'''
    if len(iterables) == 0:
        yield ()
        return
    elif len(iterables) == 1:
        for e in iterables[0]:
            yield (e,)
    elif len(iterables) == 2:
        for e12 in iproduct2(*iterables):
            yield e12
    else:
        first, others = iterables[0], iterables[1:]
        for ef, eo in iproduct2(first, iprod(*others)):
            yield (ef,) + eo

def iproduct2(iterable1, iterable2):
    '''Cartesian product of two possibly infinite iterables'''

    it1 = iter(iterable1)
    it2 = iter(iterable2)

    elems1 = []
    elems2 = []

    sentinel = object()
    def append(it, elems):
        e = next(it, sentinel)
        if e is not sentinel:
            elems.append(e)

    n = 0
    append(it1, elems1)
    append(it2, elems2)

    while n <= len(elems1) + len(elems2):
        for m in range(n-len(elems1)+1, len(elems2)):
            yield (elems1[n-m], elems2[m])
        n += 1
        append(it1, elems1)
        append(it2, elems2)

--
Oscar