Po pierwsze, Real World Haskell , który czytam, mówi, żeby nigdy nie używać foldl
i zamiast tego używać foldl'
. Więc ufam temu.
Ale jestem zamglona, gdy w użyciu foldr
w 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 inject
i 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!
źródło
fodlWhile
); 2. przekształcić go w lewy skan (scanl
) i zatrzymać go za pomocąlast . takeWhile p
lub czegoś podobnego. Uh, i 3. użyjmapAccumL
. :)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ładfoldl (flip (:)) [] [1..3] == [3,2,1]
, więcscanl (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).foldr
wygląda tak:foldl
wygląda tak:Kontekst: Złóż na wiki Haskell
źródło
Ich semantyka różni się, więc nie można po prostu zamienić
foldl
ifoldr
. 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.
źródło
Krótko mówiąc,
foldr
jest lepsze, gdy funkcja akumulatora jest leniwa na swoim drugim argumencie. Przeczytaj więcej na stronie Haskell wiki's Stack Overflow (gra słów przeznaczona).źródło
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
. Kiedyfoldl'
jest używane, suma jest obliczana natychmiast, więc zastosowaniesum
do nieskończonej listy będzie działać w nieskończoność i najprawdopodobniej w stałej przestrzeni (jeśli używasz rzeczy takich jakInt
s,Double
s,Float
s.Integer
S 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.
źródło
foldl
nic nie robi, ale stosuje konstruktory do jednego lub większej liczby swoich argumentów.foldl
jest to najlepszy wybór? (Jak nieskończone listy, kiedyfoldr
wybór jest zły, zfoldr
będąc złym wyborem dla nieskończonych list. W rzeczywistości nie powinieneś używaćfoldl
anifoldl'
dla nieskończonych list. Zobacz wiki Haskell na temat przepełnienia stosuNawiasem mówiąc, Ruby
inject
i Clojurereduce
sąfoldl
(lubfoldl1
, w zależności od używanej wersji). Zwykle, gdy w języku jest tylko jedna forma, jest to lewe zawinięcie, w tym Pythonreduce
, PerlList::Util::reduce
, C ++accumulate
, C #Aggregate
, Smalltalkinject:into:
, PHParray_reduce
, MathematicaFold
, itp. Common Lispreduce
domyślnie jest zawijany w lewo, ale jest opcja prawego zawinięcia.źródło
reduce
nie jest leniwy, więcfoldl'
i wiele z rozważań tutaj nie ma zastosowania.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?Jak podkreśla Konrad , ich semantyka jest inna. Nie mają nawet tego samego typu:
Na przykład operator dołączania listy (++) można zaimplementować za pomocą
foldr
aspodczas
wyświetli błąd typu.
źródło
foldl subtract 0 [1, 2, 3, 4]
do-10
, podczas gdy szacujefoldr subtract 0 [1, 2, 3, 4]
do-2
.foldl
jest faktycznie,0 - 1 - 2 - 3 - 4
podczas gdyfoldr
jest4 - 3 - 2 - 1 - 0
.foldr (-) 0 [1, 2, 3, 4]
jest-2
ifoldl (-) 0 [1, 2, 3, 4]
jest-10
. Z drugiej strony,subtract
jest odwrotne od tego, czego można się spodziewać (subtract 10 14
jest4
), tak samofoldr subtract 0 [1, 2, 3, 4]
jest-10
ifoldl subtract 0 [1, 2, 3, 4]
jest2
(pozytywne).