以函数式风格实现的结合函数

Question

最近，我在阅读Python的“函数式编程入门”时，发现了一个提到的标准模块test_generators.py，里面有一个生成器。

# 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

我花了一些时间才弄明白它是怎么工作的。它使用一个可变的列表values来存储迭代器产生的结果，而N+1的迭代器则返回这个values，这个过程会经过整个迭代器链。

当我在阅读函数式编程的内容时，偶然遇到了这段代码，我开始思考是否可以用函数式编程的方式重写这个连接生成器（使用itertools模块中的函数）。

在函数式风格中，有很多例程（只需看看这篇文章的食谱部分的末尾）。

但不幸的是，我没有找到任何解决方案。

那么，是否可以仅使用itertools模块来用函数式编程写这个连接生成器呢？

谢谢

Answer 1

simple_conjoin使用了和itertools中的一些小技巧一样的基本构件，比如循环、条件和yield。它还把函数当作数据来处理，这就是函数式编程的一个特点。

当然，当迭代器有副作用时，这种方法最有用。也就是说，在每个位置可以生成哪些值，取决于之前位置迭代的值。

不过，这和函数式编程的工作方式是相反的。在函数式编程中，每个函数接收输入并产生输出，和程序的其他部分没有其他的互动。

在simple_conjoin中，函数不接收输入，并且会产生副作用。这是它使用的关键。

所以，虽然你可以用函数式风格来编写它，但在简单的转换中，它不会有太大用处。

你需要想办法让它在没有副作用的情况下运行，才能真正实现“函数式”的写法。

注意：@recursive的回答很好，但如果range3有副作用，那它就不算真正的函数式了。

Answer 2

这个看起来可以用，而且它还是懒加载的：

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]))

输出结果：

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

下面是一个示例，展示了可变状态：

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

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

输出结果：（注意'x'的数量在增加）

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

如果我们使用 itertools.product 的话：

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

结果如下：

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

所以，很明显可以看出，itertools.product 会缓存迭代器返回的值。