Jak fold
s 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 f
i 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
f
nastę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ż foldl
jest wstecz, każde zastosowanie f
jest 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 f
zawsze 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 foldl
technicznie rzecz biorąc jest rekurencyjny, ponieważ całe wyrażenie wyniku jest budowane przed obliczeniem czegokolwiek, foldl
moż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 f
jest 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 f
jest 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 foldr
czasami działa na nieskończonych listach, podczas gdy foldl
nie: 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, foldr
w 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 foldr
mogę 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.
foldr
jest lepiej niżfoldl
w Haskell , podczas gdy w Erlang jest odwrotnie (czego nauczyłem się przed Haskellem ). Ponieważ Erlang nie jest leniwy i funkcje nie są curry , więcfoldl
w Erlang zachowuje się jakfoldl'
powyżej. To świetna odpowiedź! Dobra robota i dzięki!foldl
„wstecz” ifoldr
„do przodu” wydaje mi się problematyczne. Dzieje się tak częściowo dlatego, żeflip
jest to stosowane(:)
na ilustracji, dlaczego fałd jest do tyłu. Naturalną reakcją jest to, „oczywiście, że jest wstecz: Tyflip
pedałujesz konkatenację listy!” Dziwne jest również to, że nazywa się to „wstecz”, ponieważfoldl
odnosif
się najpierw do pierwszego elementu listy (najbardziej wewnętrznego) w pełnej ocenie. Chodzi o to,foldr
że „biegnie wstecz”,f
najpierw odnosząc się do ostatniego elementu.foldl
afoldr
ignorowaniem ścisłości i optymalizacji, po pierwsze oznacza „najbardziej zewnętrzny”, a nie „najbardziej wewnętrzny”. To dlategofoldr
może przetwarzać nieskończone listy, afoldl
nie może - prawe zagięcie najpierw dotyczyf
pierwszego elementu listy i (nieocenionego) wyniku zawinięcia ogona, podczas gdy lewe zagięcie musi przejść przez całą listę, aby ocenić najbardziej zewnętrzne zastosowanief
.last xs = foldl (\a z-> z) undefined xs
.itp.
Intuicyjnie
foldl
jest zawsze „na zewnątrz” lub „po lewej”, więc jest najpierw rozszerzany. Ad infinitum.źródło
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 ...
źródło
Nie znam Haskella, ale w Scheme
fold-right
zawsze „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-right
można napisać ogonowo rekurencyjnie, ale dla każdej listy cyklicznej powinieneś otrzymać przepełnienie stosu.fold-left
OTOH jest zwykle implementowane z rekurencją ogonową i po prostu utknie w nieskończonej pętli, jeśli nie zakończy jej wcześniej.źródło