Implikacje foldr vs. foldl (lub foldl ')

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!

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.

foldr wygląda tak:

foldl wygląda tak:

Kontekst: Złóż na wiki Haskell

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.

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

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.

Nawiasem mówiąc, Ruby injecti Clojure reducesą foldl(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.

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.