Что такое «питонический» эквивалент функции «складки» из функционального программирования?

119

Каков наиболее идиоматический способ добиться в Haskell чего-то вроде следующего:

foldl (+) 0 [1,2,3,4,5]
--> 15

Или его эквивалент в Ruby:

[1,2,3,4,5].inject(0) {|m,x| m + x}
#> 15

Очевидно, Python предоставляет reduceфункцию, которая является реализацией fold, точно так же, как указано выше, однако мне сказали, что «питонический» способ программирования заключался в том, чтобы избегать lambdaтерминов и функций более высокого порядка, предпочитая, где это возможно, понимание списков. Следовательно, существует ли предпочтительный способ сворачивания списка или структуры в виде списка в Python, который не является reduceфункцией, или это reduceидиоматический способ достижения этого?

мистертим
источник
2
sumнедостаточно хорошо?
JBernardo
3
не уверен, что это хороший пример для вашего вопроса. Этого легко добиться с помощью sum, возможно, вы захотите привести несколько различных типов примеров.
jamylak
14
Привет, Дж. Бернардо - Суммирование по списку чисел было задумано как довольно вырожденный пример, меня больше интересует общая идея накопления элементов списка с использованием некоторой бинарной операции и начального значения, а не конкретно суммирования целых чисел.
mistertim
1
@mistertim: sum()фактически предоставляет ограниченную функциональность. sum([[a], [b, c, d], [e, f]], [])возвращается [a, b, c, d, e, f]например.
Джоэл Корнетт
Хотя случай выполнения этого со списками является хорошей демонстрацией того, на что следует обратить внимание с помощью этой техники - +со списками - это операция с линейным временем как во времени, так и в памяти, что делает весь вызов квадратичным. Использование list(itertools.chain.from_iterable([a], [b,c,d],[e,f],[]])в целом линейно - и если вам нужно выполнить итерацию только один раз, вы можете отказаться от вызова, listчтобы сделать его постоянным с точки зрения памяти.
lvc

Ответы:

116

Пифонический способ суммирования массива использует sum. Для других целей вы можете иногда использовать некоторую комбинацию reduce(из functoolsмодуля) и operatorмодуля, например:

def product(xs):
    return reduce(operator.mul, xs, 1)

Имейте в виду, что в терминах Haskell reduceэто на самом деле foldl. Нет специального синтаксиса для выполнения сверток, нет встроенных функций foldr, и на самом деле использование reduceс неассоциативными операторами считается плохим стилем.

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

Фред Фу
источник
4
@JBernardo: вы говорите, что все, что не во встроенном модуле, не является питоническим?
Fred Foo
4
Нет, это было бы глупо сказать. Но дайте мне единственную причину, почему, по вашему мнению, GvR так сильно возненавидел бы функцию сокращения в момент ее удаления из встроенных команд?
JBernardo
6
@JBernardo: потому что люди пытаются слишком умно разыгрывать его. Процитируем из этого сообщения в блоге: «Применимость в reduce()значительной степени ограничена ассоциативными операторами, а во всех остальных случаях лучше явно прописать цикл накопления». Таким образом, его использование ограничено, но даже GvR, очевидно, должен был признать его достаточно полезным, чтобы оставить его в стандартной библиотеке.
Fred Foo
13
@JBernardo, значит ли это, что любое использование фолда в Haskell и Scheme одинаково плохо? Это просто другой стиль программирования, игнорировать его, засовывать пальцы в уши и говорить, что он неясен, не значит. Как и к большинству вещей, относящихся к другому стилю, к нему нужно привыкнуть . Идея состоит в том, чтобы разбить вещи на общие категории, чтобы было легче рассуждать о программах. «О, я хочу сделать это, хм, похоже, это складка» (или карта, или разворачивание, или разворачивание, затем складка поверх этого)
Уэс
3
Лямбда в Python не может содержать более одного выражения. Вы не можете сделать это сложным, даже если очень постараетесь. Так что питонисты, которым они не нравятся, вероятно, просто не привыкли и, следовательно, не любят функциональный стиль программирования.
golem
17

Haskell

foldl (+) 0 [1,2,3,4,5]

Python

reduce(lambda a,b: a+b, [1,2,3,4,5], 0)

Очевидно, что это тривиальный пример для иллюстрации. В Python вы бы просто сделали, sum([1,2,3,4,5])и даже пуристы Haskell обычно предпочитают sum [1,2,3,4,5].

Для нетривиальных сценариев, когда нет очевидной удобной функции, идиоматический питонический подход состоит в том, чтобы явно выписать цикл for и использовать изменяемое присвоение переменных вместо использования reduceили fold.

Это совсем не функциональный стиль, а «питонический» путь. Python не предназначен для функциональных пуристов. Посмотрите, как Python отдает предпочтение исключениям для управления потоком, чтобы увидеть, насколько нефункциональный идиоматический Python.

глина
источник
12
складки полезны не только функциональным «пуристам». Это абстракции общего назначения. Рекурсивные проблемы широко распространены в вычислениях. Складки предлагают способ удалить шаблон и способ сделать рекурсивные решения безопасными на языках, которые изначально не поддерживают рекурсию. Так что очень практичная вещь. Предрассудки GvR в этой области прискорбны.
itsbruce 03
12

В Python 3 reduceбыл удален: Примечания к выпуску . Тем не менее вы можете использовать модуль functools

import operator, functools
def product(xs):
    return functools.reduce(operator.mul, xs, 1)

С другой стороны, в документации предпочтение отдается for-loop вместо reduce, следовательно:

def product(xs):
    result = 1
    for i in xs:
        result *= i
    return result
Кыр
источник
9
reduceне был удален из стандартной библиотеки Python 3. reduceпереехал в functoolsмодуль, как вы показываете.
глина
1
@clay, я просто взял фразу из примечания к выпуску Guido, но вы можете быть правы :)
Кыр
7

Начиная Python 3.8с введения выражений присваивания (PEP 572) ( :=оператор), которые дают возможность назвать результат выражения, мы можем использовать понимание списка, чтобы воспроизвести то, что в других языках называется операциями сворачивания / свертывания / сворачивания / сокращения:

Учитывая список, уменьшающую функцию и аккумулятор:

items = [1, 2, 3, 4, 5]
f = lambda acc, x: acc * x
accumulator = 1

мы можем сложить itemsс fцелью получения Результирующего accumulation:

[accumulator := f(accumulator, x) for x in items]
# accumulator = 120

или в сжатом виде:

acc = 1; [acc := acc * x for x in [1, 2, 3, 4, 5]]
# acc = 120

Обратите внимание, что на самом деле это также операция «сканирования влево», поскольку результат понимания списка представляет состояние накопления на каждом шаге:

acc = 1
scanned = [acc := acc * x for x in [1, 2, 3, 4, 5]]
# scanned = [1, 2, 6, 24, 120]
# acc = 120
Ксавье Гихот
источник
5

Вы также можете изобретать велосипед:

def fold(f, l, a):
    """
    f: the function to apply
    l: the list to fold
    a: the accumulator, who is also the 'zero' on the first call
    """ 
    return a if(len(l) == 0) else fold(f, l[1:], f(a, l[0]))

print "Sum:", fold(lambda x, y : x+y, [1,2,3,4,5], 0)

print "Any:", fold(lambda x, y : x or y, [False, True, False], False)

print "All:", fold(lambda x, y : x and y, [False, True, False], True)

# Prove that result can be of a different type of the list's elements
print "Count(x==True):", 
print fold(lambda x, y : x+1 if(y) else x, [False, True, True], 0)
Фредерик
источник
Вы меняете аргументы fв своем рекурсивном случае.
KayEss
7
Поскольку в Python отсутствует хвостовая рекурсия, это приведет к разбивке по более длинным спискам и будет расточительным. Более того, это не совсем функция «сворачивания», а просто левый сверток, то есть foldl, то есть именно то , что reduceуже предлагает (обратите внимание, что сигнатура функции reduce reduce(function, sequence[, initial]) -> value- она ​​также включает в себя функцию задания начального значения для аккумулятор).
cemper93
5

Не совсем ответ на вопрос, но однострочные для foldl и foldr:

a = [8,3,4]

## Foldl
reduce(lambda x,y: x**y, a)
#68719476736

## Foldr
reduce(lambda x,y: y**x, a[::-1])
#14134776518227074636666380005943348126619871175004951664972849610340958208L
Мехди Неллен
источник
3
Я думаю , что это лучший способ , чтобы написать foldr: reduce(lambda y, x: x**y, reversed(a)). Теперь он имеет более естественное использование, работает с итераторами и потребляет меньше памяти.
Mateen Ulhaq
2

Фактический ответ на эту проблему (сокращение): просто используйте цикл!

initial_value = 0
for x in the_list:
    initial_value += x #or any function.

Это будет быстрее, чем сокращение, и такие вещи, как PyPy, могут оптимизировать такие циклы.

Кстати, случай суммы следует решать с помощью sumфункции

JBernardo
источник
5
Это не будет считаться питоническим для такого примера, как этот.
jamylak
7
Циклы Python заведомо медленные. Использование (или злоупотребление) reduce- распространенный способ оптимизации программы Python.
Fred Foo
2
@larsmans Пожалуйста, не говорите, что сокращение выполняется быстрее, чем простой цикл ... У него всегда будут накладные расходы на вызов функции для каждой итерации. Кроме того, Pypy снова может оптимизировать циклы до скорости C
JBernardo
1
@JBernardo: да, я это утверждаю. Я только что сравнил свою версию с версией productв вашем стиле, и она быстрее (хотя и незначительно).
Fred Foo
1
@JBernardo Предполагая встроенную функцию (например, operator.add) в качестве аргумента для уменьшения: этот дополнительный вызов - это вызов C (который намного дешевле, чем вызов Python), и он экономит отправку и интерпретацию пары инструкций байт-кода, которые могут легко вызвать десятки вызовы функций.
1

Я считаю, что некоторые из респондентов, ответивших на этот вопрос, упустили из виду более широкий смысл foldфункции как абстрактного инструмента. Да, sumможно сделать то же самое со списком целых чисел, но это тривиальный случай. foldявляется более общим. Это полезно, когда у вас есть последовательность структур данных различной формы и вы хотите четко выразить агрегирование. Поэтому вместо того, чтобы создаватьfor цикл с агрегированной переменной и каждый раз вручную пересчитывать ее, foldфункция (или версия Python, которая, по- reduceвидимому, соответствует) позволяет программисту гораздо более четко выразить намерение агрегирования, просто предоставив две вещи:

  • Начальное или «начальное» значение по умолчанию для агрегирования.
  • Функция, которая принимает текущее значение агрегации (начиная с «начального») и следующий элемент в списке и возвращает следующее значение агрегации.
rq_
источник
Привет, rq_! Я думаю, ваш ответ был бы улучшен и добавил бы много, если бы вы привели нетривиальный пример того, foldчто трудно сделать чисто на Python, а затем " fold" это на Python :-)
Скотт Скилс
0

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

def foldr(func):
    def accumulator(acc):
        def listFunc(l):
            if l:
                x = l[0]
                xs = l[1:]
                return func(x)(foldr(func)(acc)(xs))
            else:
                return acc
        return listFunc
    return accumulator  


def curried_add(x):
    def inner(y):
        return x + y
    return inner

def curried_mult(x):
    def inner(y):
        return x * y
    return inner

print foldr(curried_add)(0)(range(1, 6))
print foldr(curried_mult)(1)(range(1, 6))

Несмотря на то, что реализация рекурсивная (может быть медленной), она распечатает значения 15и 120соответственно

Брюки
источник