Haskell używa leniwej oceny do implementacji rekurencji, więc traktuje wszystko jako obietnicę dostarczenia wartości w razie potrzeby (nazywa się to thunk). Thunks są zmniejszane tylko o tyle, o ile jest to konieczne do kontynuowania, nie więcej. Przypomina to sposób matematycznego upraszczania wyrażenia, więc warto pomyśleć o tym w ten sposób. Fakt, że kolejność oceny nie jest określona w Twoim kodzie, umożliwia kompilatorowi wykonanie wielu sprytniejszych optymalizacji niż tylko eliminacja wywołań końcowych, do których jesteś przyzwyczajony. Skompiluj z, -O2jeśli chcesz optymalizacji!
Zobaczmy, jak oceniamy facSlow 5jako studium przypadku:
facSlow 5
5 * facSlow 4
5 * (4 * facSlow 3)
5 * (4 * (3 * facSlow 2))
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120
Tak więc, tak jak się martwiłeś, mamy nagromadzenie liczb przed wykonaniem jakichkolwiek obliczeń, ale w przeciwieństwie do ciebie, martwisz się, że nie ma stosu facSlowwywołań funkcji czekających na zakończenie - każda redukcja jest stosowana i znika, pozostawiając ramkę stosu w swoim wake (to znaczy, ponieważ (*)jest ścisłe, a więc uruchamia ocenę drugiego argumentu).
Funkcje rekurencyjne Haskella nie są oceniane w bardzo rekurencyjny sposób! Jedynym stosem wywołań wiszących w pobliżu są same mnożenia. Jeśli (*)jest postrzegany jako ścisły konstruktor danych, jest to tak zwane rekursję chronioną (chociaż zwykle określa się ją jako taką w przypadku nieograniczonych konstruktorów danych, gdzie to, co po nim pozostaje, to konstruktory danych - gdy są wymuszane przez dalszy dostęp).
Spójrzmy teraz na rekurencyjny ogon fac 5:
fac 5
fac' 5 1
fac' 4 {5*1}
fac' 3 {4*{5*1}}
fac' 2 {3*{4*{5*1}}}
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}
(2*{3*{4*{5*1}}})
(2*(3*{4*{5*1}}))
(2*(3*(4*{5*1})))
(2*(3*(4*(5*1))))
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120
Możesz więc zobaczyć, jak sama rekurencja ogona nie zaoszczędziła ci czasu ani miejsca. Nie tylko wymaga więcej kroków niż ogólnie facSlow 5, ale także tworzy zagnieżdżoną pozycję (pokazaną tutaj jako {...}) - wymagającą dodatkowej przestrzeni - która opisuje przyszłe obliczenia, zagnieżdżone mnożenia do wykonania.
Ten thunk następnie rozplatany przechodzenia go do dołu, ponowne obliczenie na stosie. Istnieje również niebezpieczeństwo spowodowania przepełnienia stosu przy bardzo długich obliczeniach dla obu wersji.
Jeśli chcemy to ręcznie zoptymalizować, wszystko, co musimy zrobić, to uściślić to. Do $!zdefiniowania można użyć ścisłego operatora aplikacji
facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
facS' 1 y = y
facS' x y = facS' (x-1) $! (x*y)
To zmusza facS'do ścisłości w drugim argumencie. (Jest już ścisły w pierwszym argumencie, ponieważ należy go ocenić, aby zdecydować, którą definicję facS'zastosować.)
Czasami surowość może ogromnie pomóc, czasami jest to duży błąd, ponieważ lenistwo jest bardziej wydajne. Oto dobry pomysł:
facSlim 5
facS' 5 1
facS' 4 5
facS' 3 20
facS' 2 60
facS' 1 120
120
Myślę, że to właśnie chciałeś osiągnąć.
Podsumowanie
- Jeśli chcesz zoptymalizować swój kod, pierwszym krokiem jest skompilowanie z
-O2
- Rekurencja ogonowa jest dobra tylko wtedy, gdy nie ma nagromadzenia myśli, a dodanie ścisłości zwykle pomaga temu zapobiec, jeśli i gdzie jest to stosowne. Dzieje się tak, gdy tworzysz wynik, który jest potrzebny później na raz.
- Czasami rekurencja ogonowa jest złym planem, a rekursja strzeżona jest lepszym rozwiązaniem, tj. Gdy tworzony wynik będzie potrzebny kawałek po kawałku, w częściach. Zobacz to pytanie o
foldr, a foldlna przykład i przetestować je przed sobą.
Wypróbuj te dwa:
length $ foldl1 (++) $ replicate 1000
"The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000
"The number of reductions performed is more important than tail recursion!!!"
foldl1jest rekurencyjny ogon, podczas gdy foldr1wykonuje rekursję chronioną, dzięki czemu pierwsza pozycja jest natychmiast przedstawiana do dalszego przetwarzania / dostępu. (Pierwszy „nawiasy” od razu po lewej stronie (...((s+s)+s)+...)+s, wymuszając pełną listę danych wejściowych do końca i budując dużą część przyszłych obliczeń znacznie wcześniej niż potrzebne są pełne wyniki; drugi nawias stopniowo w prawo s+(s+(...+(s+s)...)), zużywając dane wejściowe lista kawałek po kawałku, więc całość może działać w stałej przestrzeni, z optymalizacjami).
Może być konieczne dostosowanie liczby zer w zależności od używanego sprzętu.