Conjoin function made in functional style

Recently, reading Python "Functional Programming HOWTO", I came across a mentioned there test_generators.py standard module, where I found the following generator:

# conjoin is a simple backtracking generator, named in honor of Icon's
# "conjunction" control structure.  Pass a list of no-argument functions
# that return iterable objects.  Easiest to explain by example:  assume the
# function list [x, y, z] is passed.  Then conjoin acts like:
#
# def g():
#     values = [None] * 3
#     for values[0] in x():
#         for values[1] in y():
#             for values[2] in z():
#                 yield values
#
# So some 3-lists of values *may* be generated, each time we successfully
# get into the innermost loop.  If an iterator fails (is exhausted) before
# then, it "backtracks" to get the next value from the nearest enclosing
# iterator (the one "to the left"), and starts all over again at the next
# slot (pumps a fresh iterator).  Of course this is most useful when the
# iterators have side-effects, so that which values *can* be generated at
# each slot depend on the values iterated at previous slots.

def simple_conjoin(gs):

    values = [None] * len(gs)

    def gen(i):
        if i >= len(gs):
            yield values
        else:
            for values[i] in gs[i]():
                for x in gen(i+1):
                    yield x

    for x in gen(0):
        yield x

It took me a while to understand how it works. It uses a mutable list values to store the yielded results of the iterators, and the N+1 iterator return the values, which passes through the whole chain of the iterators.

As I stumbled into this code while reading about functional programming, I started thinking if it was possible to rewrite this conjoin generator using functional programming (using functions from the itertools module). There are a lot of routines written in functional style (just glance at the end of this article in the Recipes s开发者_高级运维ection).

But, unfortunately, I haven't found any solution.

So, is it possible to write this conjoin generator using functional programming just using the itertools module?

Thanks

This seems to work, and it's still lazy:

def conjoin(gs):
    return [()] if not gs else (
        (val,) + suffix for val in gs[0]() for suffix in conjoin(gs[1:])
    )

def range3():
    return range(3)

print list(conjoin([range3, range3]))

Output:

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

Example usage to show mutable state:

x = ""
def mutablerange():
    global x
    x += "x"
    return [x + str(i) for i in range(3)]

print list(conjoin([range3, mutablerange]))

Output: (watch the increasing number of 'x's)

[(0, 'x0'), (0, 'x1'), (0, 'x2'), (1, 'xx0'), (1, 'xx1'), (1, 'xx2'), (2, 'xxx0'), (2, 'xxx1'), (2, 'xxx2')]

And if we use itertools.product:

x = ""
print list(itertools.product(range3(), mutablerange()))

the result is the following:

[(0, 'x0'), (0, 'x1'), (0, 'x2'), (1, 'x0'), (1, 'x1'), (1, 'x2'), (2, 'x0'), (2, 'x1'), (2, 'x2')]

So, one clearly see, that itertools.product caches the values returned by the iterator.

simple_conjoin uses the same basic building blocks -- loops, conditions, and yield -- as the building blocks of the itertools recipes. It also treats functions as data, a hallmark of functional programming.

Of course this is most useful when the iterators have side-effects, so that which values can be generated at each slot depend on the values iterated at previous slots.

This, however, is contrary to the way functional programming works. In functional programming, each function takes input and produces output, and reacts with the rest of the program in no other way.

In simple_conjoin, the functions take no input, and have side effects. This is central to it's use.

So while you can certainly write it in functional style, it won't be useful in simple translation.

You'd need to figure out a way to write it so it operated without side effects before you could produce a truly "functional" implementation.

Note: @recursive's answer is good, but if range3 had side effects it wouldn't be truly functional.