How to iterate through the infinite Cartesian product of infinite generator functions in python?

Question

I want a generator function product that generates the Cartesian product of any two given generator functions f and g (i.e. if x can found in f() in finite time and y can be found in g() in finite time, then (x,y) should be produced from product(f, g) in finite time).

For example, I might want a generator function to iterate through (x,y) satisfying x in itertools.count() and y in itertools.count(-1, -1).

What is a good way to do this? Any order is fine.

Answer 1

Based on Gavin's earlier self-product solution, this progresses by expanding the "square" of visited pairs (if you imagine them laid out in 2D, one axis for the first generator and the other for the other).

from itertools import count, repeat

def product(f, g):
    for i, x, y in zip(count(), f(), g()):
        yield from zip(repeat(x, i), g())
        yield from zip(f(), repeat(y, i+1))

Demo, the product of the positive ints and the negative ints:

for p in product(lambda: count(1), lambda: count(-1, -1)):
    print(p)

Output (Try it online!):

(1, -1)
(2, -1)
(1, -2)
(2, -2)
(3, -1)
(3, -2)
(1, -3)
(2, -3)
(3, -3)
(4, -1)
(4, -2)
(4, -3)
(1, -4)
(2, -4)
(3, -4)
(4, -4)
(5, -1)
...