Implikacje foldr vs. foldl (lub foldl ')

155

Po pierwsze, Real World Haskell , który czytam, mówi, żeby nigdy nie używać foldli zamiast tego używać foldl'. Więc ufam temu.

Ale jestem zamglona, gdy w użyciu foldrw porównaniu foldl'. Chociaż widzę strukturę ich działania inaczej ułożoną przede mną, jestem zbyt głupi, by zrozumieć, kiedy „co jest lepsze”. Wydaje mi się, że nie powinno mieć znaczenia, który jest używany, ponieważ oba dają tę samą odpowiedź (prawda?). Faktycznie, moje poprzednie doświadczenia z tą konstrukcją pochodzą z Ruby injecti Clojure reduce, które wydają się nie mieć wersji „lewej” i „prawej”. (Pytanie poboczne: której wersji używają?)

Każdy wgląd, który może pomóc pokrzywdzonemu sprytowi, jak ja, byłby bardzo wdzięczny!

J Cooper
źródło

Odpowiedzi:

174

Rekurencja dla foldr f x ysgdzie ys = [y1,y2,...,yk]wygląda

f y1 (f y2 (... (f yk x) ...))

podczas gdy foldl f x yswygląda rekursja dla

f (... (f (f x y1) y2) ...) yk

Ważna różnica polega na tym, że jeśli wynik f x ymożna obliczyć przy użyciu tylko wartości x, to foldrnie ma potrzeby sprawdzania całej listy. Na przykład

foldr (&&) False (repeat False)

zwraca, Falsepodczas gdy

foldl (&&) False (repeat False)

nigdy się nie kończy. (Uwaga: repeat Falsetworzy nieskończoną listę, w której znajduje się każdy elementFalse ).

Z drugiej strony foldl'jest rekurencyjny i ścisły. Jeśli wiesz, że będziesz musiał przejść przez całą listę bez względu na wszystko (np. Sumując liczby na liście), to foldl'jest bardziej wydajne pod względem przestrzeni (i prawdopodobnie czasu) niż foldr.

Chris Conway
źródło
2
W foldr szacuje jako f y1 thunk, więc zwraca False, jednak w foldl f nie może znać żadnego ze swoich parametrów. za duży. foldl 'może zredukować thunk natychmiast po wykonaniu.
Sawyer
25
Aby uniknąć nieporozumień, zwróć uwagę, że nawiasy nie pokazują rzeczywistej kolejności oceny. Ponieważ Haskell jest leniwy, najpierw zostaną ocenione najbardziej zewnętrzne wyrażenia.
Lii
Dobra odpowiedź. Chciałbym dodać, że jeśli chcesz spasować, który może zatrzymać się w części listy, musisz użyć foldr; chyba że się mylę, lewe fałdy nie mogą zostać zatrzymane. (Wskazujesz na to, mówiąc „jeśli wiesz… przejdziesz… przez całą listę”). Należy również zmienić literówkę „używając tylko wartości” na „używając tylko wartości”. Tj. Usuń słowo „włączone”. (Stackoverflow nie pozwolił mi przesłać zmiany o 2 znaki!).
Lqueryvg
@Lqueryvg dwa sposoby na zatrzymanie zagięć w lewo: 1. zakoduj fałdowanie w prawo (zobacz fodlWhile); 2. przekształcić go w lewy skan ( scanl) i zatrzymać go za pomocą last . takeWhile plub czegoś podobnego. Uh, i 3. użyj mapAccumL. :)
Will Ness,
1
@Desty, ponieważ tworzy nową część swojego ogólnego wyniku na każdym kroku - w przeciwieństwie do tego foldl, że zbiera ogólny wynik i generuje go dopiero po zakończeniu całej pracy i nie ma więcej czynności do wykonania. Na przykład foldl (flip (:)) [] [1..3] == [3,2,1], więc scanl (flip(:)) [] [1..] = [[],[1],[2,1],[3,2,1],...]... IOW, foldl f z xs = last (scanl f z xs)a nieskończone listy nie mają ostatniego elementu (który w powyższym przykładzie byłby sam w sobie nieskończoną listą, od INF do 1).
Will Ness
57

foldr wygląda tak:

Wizualizacja składana w prawo

foldl wygląda tak:

Wizualizacja składana w lewo

Kontekst: Złóż na wiki Haskell

Greg Bacon
źródło
33

Ich semantyka różni się, więc nie można po prostu zamienić foldli foldr. Jedna składa elementy z lewej strony, druga z prawej. W ten sposób operator jest stosowany w innej kolejności. Ma to znaczenie dla wszystkich operacji niezespolonych, takich jak odejmowanie.

Haskell.org zawiera interesujący artykuł na ten temat.

Konrad Rudolph
źródło
Ich semantyka różni się tylko w trywialny sposób, czyli w praktyce bez znaczenia: kolejność argumentów używanej funkcji. Więc pod względem interfejsu nadal liczą się jako wymienne. Wydaje się, że prawdziwa różnica polega tylko na optymalizacji / implementacji.
Evi1M4chine,
2
@ Evi1M4chine Żadna z różnic nie jest trywialna. Wręcz przeciwnie, są one istotne (i tak, w praktyce znaczące). W rzeczywistości, gdybym miał dzisiaj napisać tę odpowiedź, jeszcze bardziej podkreśliłby tę różnicę.
Konrad Rudolph,
23

Krótko mówiąc, foldrjest lepsze, gdy funkcja akumulatora jest leniwa na swoim drugim argumencie. Przeczytaj więcej na stronie Haskell wiki's Stack Overflow (gra słów przeznaczona).

Mattiast
źródło
18

Powód foldl'jest preferowanyfoldl przypadku 99% wszystkich zastosowań, ponieważ może on działać w stałej przestrzeni dla większości zastosowań.

Weź funkcję sum = foldl['] (+) 0. Kiedy foldl'jest używane, suma jest obliczana natychmiast, więc zastosowanie sumdo nieskończonej listy będzie działać w nieskończoność i najprawdopodobniej w stałej przestrzeni (jeśli używasz rzeczy takich jak Ints, Doubles, Floats. IntegerS użyje więcej niż stałej przestrzeni, jeśli liczba staje się większa niżmaxBound :: Int ).

Z foldl programu buduje się wątek (jak przepis na uzyskanie odpowiedzi, który można ocenić później, zamiast przechowywać odpowiedź). Te pliki mogą zajmować dużo miejsca, aw tym przypadku znacznie lepiej jest ocenić wyrażenie niż przechowywać go (co prowadzi do przepełnienia stosu… i prowadzi do… och nieważne)

Mam nadzieję, że to pomoże.

Axman6
źródło
1
Dużym wyjątkiem jest sytuacja, gdy funkcja przekazana do foldlnic nie robi, ale stosuje konstruktory do jednego lub większej liczby swoich argumentów.
dfeuer
Czy istnieje ogólny wzorzec określający, kiedy foldljest to najlepszy wybór? (Jak nieskończone listy, kiedy foldrwybór jest zły, z
punktu widzenia
@ Evi1M4chine nie jestem pewien, co masz na myśli, foldrbędąc złym wyborem dla nieskończonych list. W rzeczywistości nie powinieneś używać foldlani foldl'dla nieskończonych list. Zobacz wiki Haskell na temat przepełnienia stosu
Kevin lub
14

Nawiasem mówiąc, Ruby injecti Clojure reducefoldl(lub foldl1, w zależności od używanej wersji). Zwykle, gdy w języku jest tylko jedna forma, jest to lewe zawinięcie, w tym Python reduce, Perl List::Util::reduce, C ++ accumulate, C # Aggregate, Smalltalk inject:into:, PHP array_reduce, Mathematica Fold, itp. Common Lisp reducedomyślnie jest zawijany w lewo, ale jest opcja prawego zawinięcia.

newacct
źródło
2
Ten komentarz jest pomocny, ale doceniłbym źródła.
Titaniumdecoy
Zwykły Lisp reducenie jest leniwy, więc foldl'i wiele z rozważań tutaj nie ma zastosowania.
MicroVirus
Myślę, że masz na myśli foldl', ponieważ są to surowe języki, nie? W przeciwnym razie nie oznacza to, że wszystkie te wersje powodują przepełnienie stosu, takie jakfoldl ma miejsce?
Evi1M4chine,
6

Jak podkreśla Konrad , ich semantyka jest inna. Nie mają nawet tego samego typu:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci> 

Na przykład operator dołączania listy (++) można zaimplementować za pomocą foldras

(++) = flip (foldr (:))

podczas

(++) = flip (foldl (:))

wyświetli błąd typu.

Jonas
źródło
Ich typ jest taki sam, po prostu zamieniony, co nie ma znaczenia. Ich interfejs i wyniki są takie same, z wyjątkiem nieprzyjemnego problemu P / NP (czytaj: nieskończone listy). ;) Optymalizacja ze względu na implementację to jedyna różnica w praktyce, o ile wiem.
Evi1M4chine,
@ Evi1M4chine To jest niepoprawne, spójrz na ten przykład: szacuje foldl subtract 0 [1, 2, 3, 4]do -10, podczas gdy szacuje foldr subtract 0 [1, 2, 3, 4]do -2. foldljest faktycznie, 0 - 1 - 2 - 3 - 4podczas gdy foldrjest 4 - 3 - 2 - 1 - 0.
krapht
@krapht, foldr (-) 0 [1, 2, 3, 4]jest -2i foldl (-) 0 [1, 2, 3, 4]jest -10. Z drugiej strony, subtractjest odwrotne od tego, czego można się spodziewać ( subtract 10 14jest 4), tak samo foldr subtract 0 [1, 2, 3, 4]jest -10i foldl subtract 0 [1, 2, 3, 4]jest 2(pozytywne).
pianoJames