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

118

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?

mistertim
źródło
2
sumnie jest wystarczająco dobry?
JBernardo
3
nie jestem pewien, czy to dobry przykład dla twojego pytania. Można to łatwo osiągnąć sum, możesz podać kilka różnych typów przykładów.
jamylak
14
Hej JBernardo - Podsumowując listę liczb, pomyślano jako raczej zdegenerowany przykład, bardziej interesuje mnie ogólna idea gromadzenia elementów listy za pomocą jakiejś operacji binarnej i wartości początkowej, a nie konkretnie sumowania liczb całkowitych.
mistertim
1
@mistertim: w sum()rzeczywistości zapewnia ograniczoną funkcjonalność w tym. sum([[a], [b, c, d], [e, f]], [])zwraca [a, b, c, d, e, f]na przykład.
Joel Cornett
Chociaż przypadek robienia tego z listami jest dobrą demonstracją rzeczy, na które należy uważać za pomocą tej techniki - +na listach jest liniowa operacja czasowa zarówno w czasie, jak i w pamięci, dzięki czemu całe wywołanie jest kwadratowe. Używanie list(itertools.chain.from_iterable([a], [b,c,d],[e,f],[]])jest ogólnie liniowe - i jeśli potrzebujesz powtórzyć to tylko raz, możesz porzucić wywołanie, listaby było stałe pod względem pamięci.
lvc

Odpowiedzi:

116

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.

Fred Foo
źródło
4
@JBernardo: mówisz, że wszystko, czego nie ma w module wbudowanym, nie jest w Pythonie?
Fred Foo
4
Nie, to byłoby głupie. Ale daj mi jeden powód, dlaczego myślisz, że GvR nienawidziłby tak bardzo funkcji redukującej w momencie usuwania jej z wbudowanych?
JBernardo
6
@JBernardo: ponieważ ludzie próbują robić z nim zbyt sprytne sztuczki. Cytując z tego posta na blogu, „możliwość zastosowania reduce()jest w zasadzie ograniczona do operatorów asocjacyjnych, a we wszystkich innych przypadkach lepiej jest wyraźnie napisać pętlę akumulacji”. Tak więc jego użycie jest ograniczone, ale najwyraźniej nawet GvR musiał przyznać, że jest na tyle użyteczny, aby utrzymać go w standardowej bibliotece.
Fred Foo
13
@JBernardo, czy to oznacza, że ​​każde użycie fold w Haskell i Scheme jest równie złe? To po prostu inny styl programowania, ignorowanie go, wkładanie palców do uszu i mówienie, że jest niejasne, nie oznacza, że ​​tak jest. Podobnie jak w przypadku większości rzeczy, które mają inny styl , przyzwyczajenie się do tego wymaga praktyki . Chodzi o to, aby umieścić rzeczy w ogólnych kategoriach, aby łatwiej było wnioskować o programach. „Och, chcę to zrobić, hmm, wygląda jak spasowanie” (albo mapa, albo rozwinięcie, albo rozwinięcie, a potem zagięcie)
Wes
3
Lambda w Pythonie nie może zawierać więcej niż jednego wyrażenia. Nie możesz tego skomplikować, nawet jeśli bardzo się starasz. Więc Pythonistas, którzy ich nie lubią, prawdopodobnie nie są do tego przyzwyczajeni i dlatego nie lubią funkcjonalnego stylu programowania.
golem
17

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.

glina
źródło
12
fałdy są przydatne nie tylko dla funkcjonalnych „purystów”. Są to abstrakcje ogólnego przeznaczenia. Problemy rekurencyjne są wszechobecne w komputerach. Fałdy oferują sposób na usunięcie standardowego schematu i sposób na zapewnienie bezpieczeństwa rozwiązań rekurencyjnych w językach, które natywnie nie obsługują rekurencji. A więc bardzo praktyczna rzecz. Uprzedzenia GvR w tej dziedzinie są niefortunne.
itsbruce
12

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
Kyr
źródło
9
reducenie został usunięty ze standardowej biblioteki Python 3. reduceprzeniesiony do functoolsmodułu, jak pokazujesz.
glina
1
@clay, właśnie wziąłem frazę z informacji o wydaniu Guido, ale możesz mieć rację :)
Kyr
7

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
Xavier Guihot
źródło
5

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)
Frédéric
źródło
W fswoim przypadku rekurencyjnym zamieniasz argumenty na około.
KayEss
7
Ponieważ w Pythonie brakuje rekurencji ogonowej, będzie to przerywać na dłuższych listach i jest marnotrawstwem. Co więcej, nie jest to tak naprawdę funkcja „fold”, a jedynie lewy fałd, tj. Foldl, czyli dokładnie to , co reducejuż oferuje (zauważ, że sygnatura funkcjiredred to reduce(function, sequence[, initial]) -> value- zawiera również funkcjonalność polegającą na podaniu wartości początkowej dla akumulator).
cemper93
5

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
Mehdi Nellen
źródło
3
Myślę, że to lepszy sposób, aby napisać foldr: reduce(lambda y, x: x**y, reversed(a)). Ma teraz bardziej naturalne użycie, działa z iteratorami i zużywa mniej pamięci.
Mateen Ulhaq
2

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

JBernardo
źródło
5
Nie byłoby to uważane za pythonowe w przykładzie takim jak ten.
jamylak
7
Pętle Pythona są notorycznie wolne. Używanie (lub nadużywanie) reducejest powszechnym sposobem optymalizacji programu w Pythonie.
Fred Foo
2
@larsmans Proszę, nie mów, że redukcja jest szybsza niż prosta pętla ... Zawsze będzie miała narzut wywołania funkcji dla każdej iteracji. Ponadto, ponownie, Pypy może zoptymalizować pętle do prędkości C
JBernardo
1
@JBernardo: tak, to właśnie twierdzę. Właśnie sprofilowałem moją wersję productprzeciwko jednej w twoim stylu i jest szybsza (choć marginalnie).
Fred Foo
1
@JBernardo Zakładając funkcję wbudowaną (taką jak operator.add) jako argument do redukcji: To dodatkowe wywołanie to wywołanie w C (które jest znacznie tańsze niż wywołanie w Pythonie) i oszczędza wysyłanie i interpretowanie kilku instrukcji kodu bajtowego, co może z łatwością spowodować dziesiątki wywołania funkcji.
1

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.
rq_
źródło
Cześć rq_! Myślę, że twoja odpowiedź byłaby lepsza i dodałaby wiele, gdybyś podał nietrywialny przykład tego, foldco jest trudne do wykonania w Pythonie, a następnie " fold" to w Pythonie :-)
Scott Skiles
0

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

Dyszeć
źródło