Czy ktoś może wyjaśnić koncepcję zapamiętywania Haskella?

(uwaga: zadaję to pytanie, ponieważ dotyczy ono mechaniki pojęciowej, a nie problemu z kodowaniem)

Pracowałem nad małym programem, który wykorzystywał sekwencję liczb Fibonacciego w swojej równowadze, ale zauważyłem, że jeśli przekroczyłem pewną liczbę, robi się to boleśnie powolne, przeglądając trochę, natknąłem się na technikę w Haskell znaną jako Memoization: pokazali kod działający w następujący sposób:

-- Traditional implementation of fibonacci, hangs after about 30
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)

-- Memorized variant is near instant even after 10000
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

Więc moje pytanie do was brzmi: jak, a raczej dlaczego to działa?

Czy to dlatego, że jakoś udaje mu się przejrzeć większość listy przed obliczeniem? Ale jeśli haskell jest leniwy, tak naprawdę nie ma żadnych kalkulacji, które trzeba nadrobić ... Więc jak to działa?

Aby wyjaśnić mechanikę rzeczywistej zapamiętywania,

memo_fib = (map fib [1..] !!)

tworzy listę „niezgrabnych” obliczeń. Pomyśl o nich jak o nieotwartych prezentach, dopóki ich nie dotkniemy, nie uciekną.

Teraz, gdy oceniamy thunk, nigdy nie oceniamy go ponownie. Jest to właściwie jedyna forma mutacji w „normalnym” haskellu, mutacje thunks po ocenie w celu uzyskania konkretnych wartości.

Wracając do kodu, masz listę kawałków i nadal wykonujesz rekursję tego drzewa, ale rekurencja jest wykonywana przy użyciu tej listy, a kiedy element na liście jest oceniany, nigdy więcej nie jest obliczany. W ten sposób unikamy rekurencji drzewa w naiwnej funkcji Fib.

Jako stycznie interesująca uwaga, jest to szczególnie szybkie w obliczaniu szeregu liczb fibonnaci, ponieważ ta lista jest oceniana tylko raz, co oznacza, że ​​jeśli obliczysz memo_fib 10000dwa razy, drugi raz powinien być natychmiastowy. Wynika to z tego, że Haskell tylko raz przeanalizował argumenty funkcji i używasz częściowej aplikacji zamiast lambda.

TLDR: Przechowując obliczenia na liście, każdy element listy jest oceniany jeden raz, dlatego każda liczba fibonnacci jest obliczana dokładnie raz w całym programie.

Wyobrażanie sobie:

 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_5]
 -- Evaluating THUNK_5
 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_3 + THUNK_4]
 [THUNK_1, THUNK_2, THUNK_1 + THUNK_2, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 1 + 1, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 2, THUNK_4, 2 + THUNK4]
 [1, 1, 2, 1 + 2, 2 + THUNK_4]
 [1, 1, 2, 3, 2 + 3]
 [1, 1, 2, 3, 5]

Możesz więc zobaczyć, jak ocena THUNK_4jest znacznie szybsza, ponieważ jej podwyrażenia są już oceniane.

Celem zapamiętywania nigdy nie jest dwukrotne obliczenie tej samej funkcji - jest to niezwykle przydatne, aby przyspieszyć obliczenia, które są czysto funkcjonalne, tj. Bez skutków ubocznych, ponieważ dla tych proces może być całkowicie zautomatyzowany bez wpływu na poprawność. Jest to szczególnie konieczne w przypadku funkcji takich fibo, które prowadzą do rekurencji drzewa , tj. Wykładniczego wysiłku, gdy są implementowane naiwnie. (Jest to jeden z powodów, dla których liczby Fibonacciego są w rzeczywistości bardzo złym przykładem do nauczania rekurencji - prawie wszystkie implementacje demonstracyjne, które można znaleźć w samouczkach lub książkach, nie nadają się do użycia przy dużych wartościach wejściowych).

Jeśli prześledzisz przebieg wykonywania, zobaczysz, że w drugim przypadku wartość dla fib xzawsze będzie dostępna, gdy fib x+1zostanie wykonana, a system wykonawczy będzie w stanie po prostu odczytać ją z pamięci zamiast za pomocą innego wywołania rekurencyjnego, podczas gdy pierwsze rozwiązanie próbuje obliczyć większe rozwiązanie, zanim wyniki dla mniejszych wartości będą dostępne. Jest tak ostatecznie, ponieważ iterator [0..n]jest oceniany od lewej do prawej i dlatego zacznie się od 0, podczas gdy rekurencja w pierwszym przykładzie zaczyna się od, na dopiero potem pyta o n-1. To prowadzi do wielu niepotrzebnych wywołań funkcji.