Вопрос по python, list – Что такое «pythonic» эквивалентно функции «fold» из функционального программирования?

100

Какой самый идиоматичный способ достичь чего-то подобного в Haskell:

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

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

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

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

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

Ваш Ответ

7   ответов
4

a = [8,3,4]

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

## Foldr
reduce(lambda x,y: y**x, a[::-1])
#14134776518227074636666380005943348126619871175004951664972849610340958208L
Error: User Rate Limit Exceededreduce(lambda y, x: x**y, reversed(a))Error: User Rate Limit Exceeded
10

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

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

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

def product(xs):
    result = 1
    for i in xs:
        result *= i
    return result
Error: User Rate Limit Exceeded
reduceError: User Rate Limit ExceededreduceError: User Rate Limit ExceededfunctoolsError: User Rate Limit Exceeded
2

просто используйте цикл!

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

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

Кстати, сумма сумма должна быть решена сsum функция

Error: User Rate Limit ExceededreduceError: User Rate Limit Exceeded
Error: User Rate Limit ExceededproductError: User Rate Limit Exceededit's fasterError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

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 соответственно

13

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

питон

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

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

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

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

Error: User Rate Limit Exceeded
102

sum, Для других целей иногда можно использовать некоторую комбинациюreduce иoperator модуль, например

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

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededit takes practice to get used to itError: User Rate Limit Exceeded
Error: User Rate Limit ExceededGvR would hate so much the reduce functionError: User Rate Limit Exceeded
Error: User Rate Limit ExceededreduceError: User Rate Limit ExceededmapError: User Rate Limit ExceededfoldlError: User Rate Limit ExceededletError: User Rate Limit Exceeded
Error: User Rate Limit Exceededreduce()Error: User Rate Limit Exceeded
4

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)
Error: User Rate Limit ExceededexactlyError: User Rate Limit ExceededreduceError: User Rate Limit Exceededreduce(function, sequence[, initial]) -> valueError: User Rate Limit Exceeded
Error: User Rate Limit ExceededfError: User Rate Limit Exceeded

Похожие вопросы