Функция соединения выполнена в функциональном стиле

Question

Недавно, читая Python "HOWTO по функциональному программированию" , я наткнулся на упомянутый там 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

Кажется, это работает, и все еще лениво:

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

Вывод: (следите за увеличением числа х)

[(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 кэширует значения, возвращаемые итератором.

Answer 2

simple_conjoin использует те же основные строительные блоки - циклы, условия и yield - что и строительные блоки рецептов itertools. Он также рассматривает функции как данные, отличительный признак функционального программирования.

Конечно, это наиболее полезно, когда у итераторов есть побочные эффекты, так что значения можно генерировать при каждый слот зависит от значений, повторяемых в предыдущих слотах.

Это, однако, противоречит принципу функционального программирования. В функциональном программировании каждая функция принимает входные данные и производит выходные данные, и никак не реагирует с остальной частью программы.

В simple_conjoin функции не требуют ввода и имеют побочные эффекты. Это главное в его использовании.

Так что, хотя вы, конечно, можете написать в функциональном стиле, он не будет полезен в простом переводе.

Вам нужно найти способ написать его, чтобы он работал без побочных эффектов, прежде чем вы могли бы создать действительно "функциональную" реализацию.

Примечание: ответ @ recursive хорош, но если бы у range3 были побочные эффекты, он не был бы действительно функциональным.