zachowanie foldl versus foldr z nieskończonymi listami

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?

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.

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.

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

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.