Jaki jest „pythonowy” odpowiednik funkcji „fold” z programowania funkcjonalnego?

Jaki jest najbardziej idiomatyczny sposób osiągnięcia czegoś takiego w Haskellu:

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

Lub jego odpowiednik w Rubim:

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

Oczywiście Python udostępnia reducefunkcję, która jest implementacją fold, dokładnie tak, jak powyżej, jednak powiedziano mi, że „pythonowym” sposobem programowania jest unikanie lambdaterminów i funkcji wyższego rzędu, preferowanie wyrażeń listowych tam, gdzie to możliwe. W związku z tym, czy istnieje preferowany sposób zwinięcia listy lub struktury podobnej do listy w Pythonie, która nie jest reducefunkcją, czy też jest reduceidiomatycznym sposobem osiągnięcia tego?

Sposób sumowania tablicy w Pythonie polega na użyciu sum. Do innych celów można czasem użyć kombinacji reduce(z functoolsmodułu) i operatormodułu, np .:

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

Należy pamiętać, że reducejest to właściwie a foldl, w terminologii Haskella. Nie ma specjalnej składni do wykonywania zawinięć, nie ma wbudowanej foldr, a używanie reducez operatorami niezespolonymi jest uważane za zły styl.

Używanie funkcji wyższego rzędu jest dość pytoniczne; dobrze wykorzystuje zasadę Pythona, że ​​wszystko jest obiektem, łącznie z funkcjami i klasami. Masz rację, że wyrażenia lambda są mile widziane przez niektórych Pythonistów, ale głównie dlatego, że nie są zbyt czytelne, gdy stają się złożone.

Haskell

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

Pyton

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

Oczywiście jest to trywialny przykład ilustrujący sprawę. W Pythonie po prostu byś to zrobił, sum([1,2,3,4,5])a nawet puryści Haskell na ogół woleliby sum [1,2,3,4,5].

W przypadku nietrywialnych scenariuszy, w których nie ma oczywistej funkcji wygodnej, idiomatycznym podejściem w języku Python jest jawne zapisanie pętli for i użycie mutowalnego przypisania zmiennej zamiast używania reducelub fold.

To wcale nie jest styl funkcjonalny, ale jest to sposób „pythonowy”. Python nie jest przeznaczony dla funkcjonalnych purystów. Zobacz, jak Python faworyzuje wyjątki do sterowania przepływem, aby zobaczyć, jak niefunkcjonalny jest idiomatyczny Python.

W Pythonie 3 reduceusunięto: Uwagi do wydania . Niemniej jednak możesz skorzystać z modułu functools

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

Z drugiej strony w dokumentacji preferowany jest for-loop zamiast reduce, stąd:

def product(xs):
    result = 1
    for i in xs:
        result *= i
    return result

Rozpoczynając Python 3.8i wprowadzając wyrażenia przypisania (PEP 572) ( :=operator), które dają możliwość nazwania wyniku wyrażenia, możemy użyć wyrażenia listowego, aby powielić, jakie inne języki nazywają operacjami fold / foldleft / redukuj:

Mając listę, funkcję redukującą i akumulator:

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

możemy złożyć itemszf w celu uzyskania wytworzony accumulation:

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

lub w postaci skondensowanej:

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

Zauważ, że w rzeczywistości jest to również operacja „scanleft”, ponieważ wynik zrozumienia listy reprezentuje stan akumulacji na każdym kroku:

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

Możesz także odkryć koło na nowo:

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)

Niezupełnie odpowiedź na pytanie, ale jednolinijkowe dla foldl i foldr:

a = [8,3,4]

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

## Foldr
reduce(lambda x,y: y**x, a[::-1])
#14134776518227074636666380005943348126619871175004951664972849610340958208L

Właściwa odpowiedź na ten (zredukowany) problem brzmi: po prostu użyj pętli!

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

Będzie to szybsze niż redukcja, a rzeczy takie jak PyPy mogą optymalizować takie pętle.

Przy okazji, przypadek sumy należy rozwiązać za pomocą sumfunkcji

Uważam, że niektórzy respondenci tego pytania nie dostrzegli szerszego znaczenia foldfunkcji jako narzędzia abstrakcyjnego. Tak, summożna zrobić to samo dla listy liczb całkowitych, ale jest to trywialny przypadek. foldjest bardziej ogólny. Jest to przydatne, gdy masz sekwencję struktur danych o różnym kształcie i chcesz jasno wyrazić agregację. Zamiast więc tworzyć forpętlę ze zmienną zagregowaną i ręcznie przeliczać ją za każdym razem, foldfunkcja (lub wersja Pythona, która reducewydaje się odpowiadać) pozwala programiście wyrazić zamiar agregacji znacznie jaśniej, po prostu zapewniając dwie rzeczy:

• Domyślna wartość początkowa lub wartość początkowa agregacji.
• Funkcja, która pobiera bieżącą wartość agregacji (zaczynając od „ziarna”) i następny element na liście i zwraca następną wartość agregacji.

Mogę się spóźnić na imprezę, ale możemy stworzyć własny, foldrużywając prostego rachunku lambda i funkcji curry. Oto moja implementacja foldr w Pythonie.

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

Mimo że realizacja jest rekurencyjna (może być powolne), wydrukuje wartości 15i 120odpowiednio