foldl jest rekurencyjne, więc dlaczego foldr działa szybciej niż foldl?

Question

Chciałem przetestować foldl vs foldr. Z tego, co widziałem, powinieneś używać foldl over foldr, kiedy tylko możesz, ze względu na optymalizację reclinowania ogonów.

Ma to sens. Jednak po uruchomieniu tego testu jestem zdezorientowany:

foldr (trwa 0.057s przy użyciu polecenia czas):

a::a -> [a] -> [a] 
a x = ([x] ++) 

main = putStrLn(show (sum (foldr a [] [0.. 100000]))) 

foldl (trwa 0.089s przy użyciu polecenia czas):

b::[b] -> b -> [b] 
b xs = (++ xs). (\y->[y]) 

main = putStrLn(show (sum (foldl b [] [0.. 100000]))) 

Jasne jest, że ten przykład jest banalny, ale jestem zdezorientowany, dlaczego foldr bije foldl. Czy nie powinien to być oczywisty przypadek, w którym foldl wygrywa?

Answer 1

Witamy w świecie leniwego oceniania.

Kiedy myślisz o tym w kategoriach ścisłej oceny, foldl wygląda "dobrze", a foldr wygląda "źle", ponieważ foldl jest rekurencyjny, ale foldr musiałby zbudować wieżę w stosie, aby mógł przetworzyć ostatni element pierwszy.

Jednak leniwe oceny zamieniają tabele. Weźmy, na przykład, definicja funkcji mapy:

map :: (a -> b) -> [a] -> [b] 
map _ []  = [] 
map f (x:xs) = f x : map f xs 

to nie byłoby zbyt dobre, jeśli Haskell wykorzystywane szczegółową ocenę, ponieważ musiałaby obliczyć ogon, następnie dołączana element (dla wszystkich pozycji na liście). Jedynym sposobem, aby zrobić to sprawnie, wydaje się być zbudowanie elementów w odwrotnym kierunku.

Jednak dzięki leniwej ocenie Haskella ta funkcja mapy jest rzeczywiście wydajna. Listy w Haskell można uważać za generatory, a ta funkcja mapy generuje pierwszy element, stosując f do pierwszego elementu listy wejściowej. Kiedy potrzebuje drugiego przedmiotu, po prostu robi to samo (bez dodatkowej przestrzeni).

Okazuje się, że map można opisać w kategoriach foldr:

map f xs = foldr (\x ys -> f x : ys) [] xs 

Trudno powiedzieć, patrząc na niego, ale ocena leniwy rzutach ponieważ foldr może dać f swój pierwszy argument od zaraz:

foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

Ponieważ f określa map może powrócić do pierwszej pozycji na liście wpływającej wyłącznie pierwszy parametr zagięcia mogą działać leniwie CO Nstant przestrzeń.

Teraz leniwe oceny nie gryzą.Na przykład spróbuj uruchomić sumę [1..1000000]. Daje to przepełnienie stosu. Dlaczego miałby to robić? Powinien po prostu ocenić od lewej do prawej, prawda? wygląd

Miejmy na jak Haskell ocenia go:

foldl f z []  = z 
foldl f z (x:xs) = foldl f (f z x) xs 

sum = foldl (+) 0 

sum [1..1000000] = foldl (+) 0 [1..1000000] 
       = foldl (+) ((+) 0 1) [2..1000000] 
       = foldl (+) ((+) ((+) 0 1) 2) [3..1000000] 
       = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000] 
        ... 
       = (+) ((+) ((+) (...) 999999) 1000000) 

Haskell jest zbyt leniwy, aby wykonać uzupełnień jak to idzie. Zamiast tego kończy się wieżą niedoszacowanych ciosów, które muszą zostać zmuszone do zdobycia liczby. Przepełnienie stosu występuje podczas tej oceny, ponieważ musi się głęboko rekurencyjnie ocenić wszystkie uderzenia.

Na szczęście istnieje specjalna funkcja w Data.List o nazwie foldl', która działa ściśle. foldl' (+) 0 [1..1000000] nie będzie stosować przepełnienia. (Uwaga: Próbowałem zastępując foldl z foldl' w teście, ale faktycznie działać wolniej.)

Answer 2

No, niech mi przepisać swoje funkcje w sposób, że różnica powinna być oczywista -

a :: a -> [a] -> [a] 
a = (:) 

b :: [b] -> b -> [b] 
b = flip (:) 

Widać, że b jest bardziej skomplikowane niż. Jeśli chcesz być precyzyjnym, a potrzebuje jednego kroku redukcji dla wartości do obliczenia, ale b potrzebuje dwóch. To czyni różnicę czasu, którą mierzysz, w drugim przykładzie dwa razy więcej redukcji musi być wykonane.

// edit: Ale złożoność czasu jest taka sama, więc nie zawracałbym sobie tym głowy.

Answer 3

Ani foldl ani foldr ogon jest zoptymalizowany. Jest to tylko foldl'.

Ale w twoim przypadku, używając ++ z foldl' nie jest dobrym pomysłem, ponieważ kolejna ocena ++ spowoduje znowu i znowu przejeżdżające rosnące akumulator.

Answer 4

Dla a, lista [0.. 100000] musi zostać rozwinięta od razu, aby foldr mógł rozpoczynać się od ostatniego elementu. Potem jak to fałdy rzeczy razem, wyniki pośrednie są

[100000] 
[99999, 100000] 
[99998, 99999, 100000] 
... 
[0.. 100000] -- i.e., the original list 

Ponieważ nikt nie może zmienić tę wartość List (Haskell jest czysty język funkcjonalny), kompilator jest wolna do ponownego użycia wartość. Wartości pośrednie, takie jak [99999, 100000], mogą być po prostu wskaźnikami do rozwiniętej listy [0.. 100000] zamiast oddzielnych list.

dla B, spójrz na wartości pośrednich:

[0] 
[0, 1] 
[0, 1, 2] 
... 
[0, 1, ..., 99999] 
[0.. 100000] 

Każdy z tych wykazów pośrednich nie mogą być ponownie wykorzystane, bo jeśli zmieni się do końca listy, a następnie zmieniłeś żadnych innych wartości, które wskazują do tego. Tworzysz kilka dodatkowych list, które wymagają trochę czasu, aby zbudować pamięć. W tym przypadku spędzasz dużo więcej czasu na przydzielaniu i wypełnianiu tych list, które są wartościami pośrednimi.

Ponieważ właśnie robisz kopię listy, a działa szybciej, ponieważ zaczyna się od rozwinięcia pełnej listy, a następnie po prostu przesuwa wskaźnik z tyłu listy do przodu.

Answer 5

EDYCJA: Po ponownym przeanalizowaniu tego problemu, uważam, że wszystkie obecne wyjaśnienia są nieco niewystarczające, więc napisałem dłuższe wyjaśnienie.

Różnica polega na tym, w jaki sposób foldl i foldr stosują swoją funkcję redukcji. Patrząc na razie foldr, możemy go rozwinąć jako

foldr (\x -> [x] ++) [] [0..10000] 
[0] ++ foldr a [] [1..10000] 
[0] ++ ([1] ++ foldr a [] [2..10000]) 
... 

Ta lista jest przetwarzany przez sum, która zużywa go w następujący sposób:

sum = foldl' (+) 0 
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000])) 
foldl' (+) 0 (0 : [1] ++ ... ++ [10000])  -- get head of list from '++' definition 
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000]) -- add accumulator and head of list 
foldl' (+) 0 (1 : [2] ++ ... ++ [10000]) 
foldl' (+) 1 ([2] ++ ... ++ [10000]) 
... 

Mam pominięte szczegóły listy konkatenacji, ale tak właśnie postępuje redukcja. Ważną częścią jest to, że wszystko zostaje przetworzone, aby zminimalizować przechodzenie list.Tylko foldr przechodzi przez listę tylko raz, konkatenacje nie wymagają ciągłych przesuwów list, a sum ostatecznie zużywa listę w jednym przebiegu. Krytycznie, szef listy jest dostępny od foldr natychmiast do sum, więc sum może rozpocząć pracę natychmiast, a wartości mogą być gc'd podczas ich generowania. W przypadku frameworków fuzyjnych, takich jak vector, nawet pośrednie listy prawdopodobnie zostaną zfuzowane.

Kontrast to do funkcji foldl:

b xs = (++xs) . (\y->[y]) 
foldl b [] [0..10000] 
foldl b ([0] ++ []) [1..10000] 
foldl b ([1] ++ ([0] ++ [])) [2..10000] 
foldl b ([2] ++ ([1] ++ ([0] ++ []))) [3..10000] 
... 

Zauważ, że teraz na czele listy nie jest dostępna aż foldl została zakończona. Oznacza to, że cała lista musi zostać skonstruowana w pamięci, zanim sum może zacząć działać. Jest to znacznie mniej efektywne. Uruchamianie dwóch wersji z +RTS -s pokazuje nieszczęśliwą wydajność zbierania śmieci z wersji foldl.

Jest to również przypadek, w którym foldl' nie pomoże. Dodana surowość foldl' nie zmienia sposobu tworzenia listy pośredniej. Głowa listy pozostaje niedostępna do momentu, aż foldl 'zostanie zakończona, więc wynik będzie nadal wolniejszy niż z foldr.

używam następującą regułę, aby ustalić najlepszy wybór fold

• Dla fałdy, które są redukcja użyć foldl' (np będzie to jedyny/Final przechodzenie)
• W przeciwnym razie użyj foldr .
• Nie używaj foldl.

W większości przypadków najlepsza funkcja składania to foldr, ponieważ kierunek przejścia jest optymalny dla leniwej oceny list. Jest także jedynym, który może przetwarzać nieskończone listy. Dodatkowa surowość numeru foldl' może w niektórych przypadkach sprawić, że będzie on szybszy, ale zależy to od tego, jak wykorzystasz tę strukturę i jak leniwa ona jest.

Answer 6

Problem polega na tym, że optymalizacja rekurencji ogona to optymalizacja pamięci, a nie optymalizacja czasu wykonania!

Optymalizacja rekursji ogona pozwala uniknąć zapamiętania wartości dla każdego wywołania rekursywnego.

Tak, foldl jest w rzeczywistości "dobry", a foldr jest "zły".

Na przykład, biorąc pod uwagę definicje foldr i foldl:

foldl f z [] = z 
foldl f z (x:xs) = foldl f (z `f` x) xs 

foldr f z [] = z 
foldr f z (x:xs) = x `f` (foldr f z xs) 

to jak "foldl (+) 0 [1,2,3]" jest wyrażenie:

foldl (+) 0 [1, 2, 3] 
foldl (+) (0+1) [2, 3] 
foldl (+) ((0+1)+2) [3] 
foldl (+) (((0+1)+2)+3) [ ] 
(((0+1)+2)+3) 
((1+2)+3) 
(3+3) 
6 

Zauważ, że foldl nie pamięta wartości 0, 1, 2 ..., ale przekazuje całe wyrażenie ((((0 + 1) +2) +3) jako argument leniwie i nie ocenia go aż do ostatniej oceny foldl, gdzie dociera do przypadku podstawowego i zwraca wartość przekazaną jako drugi parametr (z), który nie jest jeszcze oceniany.

Z drugiej strony, to jak foldr działa:

foldr (+) 0 [1, 2, 3] 
1 + (foldr (+) 0 [2, 3]) 
1 + (2 + (foldr (+) 0 [3])) 
1 + (2 + (3 + (foldr (+) 0 []))) 
1 + (2 + (3 + 0))) 
1 + (2 + 3) 
1 + 5 
6 

Ważną różnicą jest to, że tam, gdzie foldl ocenia cały wyraz w ostatniej rozmowy, unikając konieczności wrócić do osiągnięcia zapamiętane wartości, foldr Nie. foldr zapamiętuje jedną liczbę całkowitą dla każdego połączenia i wykonuje dodawanie w każdym wywołaniu.

Należy pamiętać, że foldr i foldl nie zawsze są odpowiednikami. Na przykład, spróbuj obliczyć to wyrażenia w uścisków:

foldr (&&) True (False:(repeat True)) 

foldl (&&) True (False:(repeat True)) 

foldr i foldl są równoważne tylko w pewnych warunkach opisanych here

(przepraszam za mój zły język angielski)

Answer 7

I nie sądzę, żeby ktoś to Właściwie to odpowiedziałem na tę prawdziwą odpowiedź, chyba że czegoś mi brakuje (co może być prawdą i mile widziane z pochlebstwami).

Myślę, że największym inaczej w tym przypadku jest to, że foldr buduje listę takiego:

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000 ])))

Zważywszy foldl buduje listę takiego:

((([0] ++ [1]) ++ [2]) ++ ...) ++ [999888]) ++ [999999]) ++ [1000000]

Różnica w subtelności, ale zauważ, że w wersji foldr wersja ++ zawsze ma tylko jeden element listy jako lewy argument. Wersja foldl zawiera maksymalnie 999999 elementów w lewym argumencie ++ (średnio około 500000), ale tylko jeden element w prawym argumencie.

Jednak, ++ wymaga czasu proporcjonalnego do wielkości lewego argumentu, ponieważ musi wyglądać całą listę lewej listy do końca, a następnie ponownie wskazać ten ostatni element pierwszemu elementowi prawego argumentu (w najlepszym przypadku może faktycznie musi zrobić kopię). Prawidłowa lista argumentów pozostaje niezmieniona, więc nie ma znaczenia, jaka jest duża.

Dlatego wersja foldl jest znacznie wolniejsza. Z moim zdaniem nie ma to nic wspólnego z lenistwem.