zachowanie foldl versus foldr z nieskończonymi listami

124

Kod funkcji myAny w tym pytaniu używa foldr. Przestaje przetwarzać nieskończoną listę, gdy predykat jest spełniony.

Przepisałem to używając foldl:

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(Zwróć uwagę, że argumenty funkcji step są poprawnie odwrócone).

Jednak nie przestaje już przetwarzać nieskończonych list.

Próbowałem prześledzić wykonanie funkcji, jak w odpowiedzi Apocalisp :

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

Jednak to nie jest sposób zachowania funkcji. Jak to źle?

Titaniumdecoy
źródło

Odpowiedzi:

231

Jak folds różnią wydaje się być częstym źródłem nieporozumień, więc tutaj jest bardziej ogólny przegląd:

Rozważ złożenie listy n wartości za [x1, x2, x3, x4 ... xn ]pomocą jakiejś funkcji fi ziarna z.

foldl jest:

  • Lewy asocjacyjny :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Ogon rekurencyjny : iteruje po liście, tworząc później wartość
  • Leniwy : nic nie jest oceniane, dopóki wynik nie będzie potrzebny
  • Do tyłu : foldl (flip (:)) []odwraca listę.

foldr jest:

  • Prawe skojarzenie :f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
  • Rekurencyjnie na argument : każda iteracja dotyczy fnastępnej wartości i wyniku zawinięcia pozostałej części listy.
  • Leniwy : nic nie jest oceniane, dopóki wynik nie będzie potrzebny
  • Naprzód : foldr (:) []zwraca listę niezmienioną.

Jest tutaj nieco subtelny punkt, który czasami denerwuje ludzi: ponieważ foldljest wstecz, każde zastosowanie fjest dodawane na zewnątrz wyniku; a ponieważ jest leniwy , nic nie jest oceniane, dopóki wynik nie jest wymagany. Oznacza to, że aby obliczyć dowolną część wyniku, Haskell najpierw iteruje całą listę, konstruując wyrażenie aplikacji funkcji zagnieżdżonych, a następnie ocenia najbardziej zewnętrzną funkcję, oceniając jej argumenty w razie potrzeby. Jeśli fzawsze używa pierwszego argumentu, oznacza to, że Haskell musi powtórzyć całą drogę w dół do najgłębszego członu, a następnie pracować wstecz, obliczając każde zastosowanie f.

Jest to oczywiście dalekie od efektywnej rekurencji ogonowej, którą większość funkcjonalnych programistów zna i kocha!

W rzeczywistości, nawet jeśli foldltechnicznie rzecz biorąc jest rekurencyjny, ponieważ całe wyrażenie wyniku jest budowane przed obliczeniem czegokolwiek, foldlmoże spowodować przepełnienie stosu!

Z drugiej strony, zastanów się foldr. Jest również leniwy, ale ponieważ działa do przodu , każde zastosowanie fjest dodawane do wnętrza wyniku. Tak więc, aby obliczyć wynik, Haskell konstruuje pojedynczą aplikację funkcyjną, której drugim argumentem jest reszta listy składanej. Jeśli fjest leniwy w swoim drugim argumencie - na przykład konstruktorze danych - wynik będzie przyrostowo leniwy , a każdy krok zwinięcia będzie obliczany tylko wtedy, gdy określona część wyniku, która tego wymaga.

Widzimy więc, dlaczego foldrczasami działa na nieskończonych listach, podczas gdy foldlnie: pierwsza może leniwie przekształcić nieskończoną listę w inną leniwą nieskończoną strukturę danych, podczas gdy druga musi sprawdzić całą listę, aby wygenerować dowolną część wyniku. Z drugiej strony, foldrw przypadku funkcji, która potrzebuje natychmiast obu argumentów, na przykład (+)działa (a raczej nie działa) bardzo podobnie foldl, buduje ogromne wyrażenie przed jego oszacowaniem.

Zatem dwie ważne kwestie, na które należy zwrócić uwagę, to:

  • foldr może przekształcić jedną leniwą rekurencyjną strukturę danych w inną.
  • W przeciwnym razie leniwe fałdy ulegną awarii z przepełnieniem stosu na dużych lub nieskończonych listach.

Być może zauważyłeś, że wygląda na to, że foldrmogę zrobić wszystko foldl, co może, a także więcej. To prawda! W rzeczywistości foldl jest prawie bezużyteczny!

Ale co, jeśli chcemy uzyskać nieleniwy wynik, zawijając dużą (ale nie nieskończoną) listę? W tym celu chcemy ścisłej fałdy , którą jednak standardowe biblioteki zapewniają :

foldl' jest:

  • Lewy asocjacyjny :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Ogon rekurencyjny : iteruje po liście, tworząc później wartość
  • Ścisłe : każda aplikacja funkcji jest oceniana po drodze
  • Do tyłu : foldl' (flip (:)) []odwraca listę.

Ponieważ foldl'jest ścisłe , aby obliczyć wynik, Haskell oceni f na każdym kroku, zamiast pozwolić, aby lewy argument zgromadził ogromne, nieocenione wyrażenie. To daje nam zwykłą, wydajną rekurencję ogonową, jakiej chcemy! Innymi słowy:

  • foldl' może efektywnie składać duże listy.
  • foldl' zawiesi się w nieskończonej pętli (nie spowoduje przepełnienia stosu) na nieskończonej liście.

Wiki Haskell również ma stronę omawiającą to zagadnienie.

CA McCann
źródło
6
Przyjechałem tutaj, ponieważ jestem ciekaw, dlaczego foldrjest lepiej niż foldlw Haskell , podczas gdy w Erlang jest odwrotnie (czego nauczyłem się przed Haskellem ). Ponieważ Erlang nie jest leniwy i funkcje nie są curry , więc foldlw Erlang zachowuje się jak foldl'powyżej. To świetna odpowiedź! Dobra robota i dzięki!
Siu Ching Pong -Asuka Kenji-
7
Jest to przeważnie świetne wyjaśnienie, ale określenie foldl„wstecz” i foldr„do przodu” wydaje mi się problematyczne. Dzieje się tak częściowo dlatego, że flipjest to stosowane (:)na ilustracji, dlaczego fałd jest do tyłu. Naturalną reakcją jest to, „oczywiście, że jest wstecz: Ty flippedałujesz konkatenację listy!” Dziwne jest również to, że nazywa się to „wstecz”, ponieważ foldlodnosi fsię najpierw do pierwszego elementu listy (najbardziej wewnętrznego) w pełnej ocenie. Chodzi o to, foldrże „biegnie wstecz”, fnajpierw odnosząc się do ostatniego elementu.
Dave Abrahams
1
@DaveAbrahams: Pomiędzy tylko foldla foldrignorowaniem ścisłości i optymalizacji, po pierwsze oznacza „najbardziej zewnętrzny”, a nie „najbardziej wewnętrzny”. To dlatego foldrmoże przetwarzać nieskończone listy, a foldlnie może - prawe zagięcie najpierw dotyczy fpierwszego elementu listy i (nieocenionego) wyniku zawinięcia ogona, podczas gdy lewe zagięcie musi przejść przez całą listę, aby ocenić najbardziej zewnętrzne zastosowanie f.
CA McCann
1
Zastanawiam się tylko, czy jest jakikolwiek przypadek, w którym foldl byłoby preferowane zamiast foldl ', myślisz, że jest taki?
kazuoua
1
@kazuoua gdzie lenistwo jest istotne, np last xs = foldl (\a z-> z) undefined xs.
Will Ness,
28
myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

itp.

Intuicyjnie foldljest zawsze „na zewnątrz” lub „po lewej”, więc jest najpierw rozszerzany. Ad infinitum.

Artelius
źródło
10

Można zobaczyć w dokumentacji Haskell jest tutaj , że foldl jest ogon rekurencyjnej i nigdy się nie skończy, jeśli przeszedł nieskończoną listę, ponieważ wymaga się od następnego parametru przed zwróceniem wartości ...

Romain
źródło
0

Nie znam Haskella, ale w Scheme fold-rightzawsze „działa” na ostatnim elemencie listy jako pierwszy. Tak więc nie będzie działać dla listy cyklicznej (która jest taka sama jak nieskończona).

Nie jestem pewien, czy fold-rightmożna napisać ogonowo rekurencyjnie, ale dla każdej listy cyklicznej powinieneś otrzymać przepełnienie stosu. fold-leftOTOH jest zwykle implementowane z rekurencją ogonową i po prostu utknie w nieskończonej pętli, jeśli nie zakończy jej wcześniej.

leppie
źródło
3
W Haskell jest inaczej z powodu lenistwa.
Lifu Huang