Kann jemand das Konzept hinter Haskells Memoisierung erklären?

(Beachten Sie, dass ich die Frage hier stelle, da es sich eher um die konzeptionelle Mechanik als um ein Codierungsproblem handelt.)

Ich arbeite an einem kleines Programm, das eine Folge von Fibonacci - Zahlen in seinem equasion Verwendung wurde, aber ich merkte , dass , wenn ich eine bestimmte Anzahl überwindet es quälend langsam bekam, googeln um ein wenig ich auf eine Technik , die in Haskell als bekannt gestolpert Memoization, Sie zeigten Code, der so funktioniert:

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

Meine Frage an euch ist also, wie oder warum funktioniert das?

Liegt es daran, dass es irgendwie gelingt, den größten Teil der Liste zu durchlaufen, bevor die Berechnung aufholt? Aber wenn Haskell faul ist, gibt es nicht wirklich eine Berechnung, die nachholen muss ... Also, wie funktioniert es?

Nur um die Mechanik hinter dem eigentlichen Auswendiglernen zu erklären,

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

erzeugt eine Liste von "Thunks", nicht ausgewerteten Berechnungen. Denken Sie an diese wie ungeöffnete Geschenke, solange wir sie nicht anfassen, laufen sie nicht.

Sobald wir einen Thunk evaluieren, evaluieren wir ihn nie wieder. Dies ist tatsächlich die einzige Form der Mutation in "normalem" Haskell. Die Thunks mutieren, sobald sie ausgewertet wurden, zu konkreten Werten.

Zurück zu Ihrem Code, Sie haben eine Liste von Thunks, und Sie führen diese Baumrekursion immer noch durch, aber Sie rekursieren mit der Liste, und sobald ein Element in der Liste ausgewertet wurde, wird es nie wieder berechnet. So vermeiden wir die Baumrekursion in der naiven Fib-Funktion.

Als tangential interessanter Hinweis ist dies besonders schnell, wenn eine Reihe von Fibonnaci-Zahlen berechnet wird, da diese Liste nur einmal ausgewertet wird. Wenn Sie also memo_fib 10000zweimal rechnen , sollte das zweite Mal sofort erfolgen. Dies liegt daran, dass Haskell Argumente für Funktionen nur einmal ausgewertet hat und Sie eine Teilanwendung anstelle eines Lambdas verwenden.

TLDR: Durch das Speichern von Berechnungen in einer Liste wird jedes Element der Liste einmal ausgewertet, daher wird jede Fibonnacci-Zahl im gesamten Programm genau einmal berechnet.

Visualisierung:

 [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]

Sie können also sehen, dass die Auswertung THUNK_4viel schneller ist, da die Unterausdrücke bereits ausgewertet wurden.

Der Punkt, an dem Sie sich merken müssen, ist, niemals dieselbe Funktion zweimal zu berechnen - dies ist äußerst nützlich, um Berechnungen zu beschleunigen, die rein funktional sind, dh ohne Nebenwirkungen, da bei diesen der Prozess vollständig automatisiert werden kann, ohne die Korrektheit zu beeinträchtigen. Dies ist insbesondere dann erforderlich , für Funktionen wie fibo, die zu führen Baumrekursion , das heißt exponentiellen Aufwand, wenn naiv implementiert. (Dies ist ein Grund, warum die Fibonacci-Zahlen eigentlich ein sehr schlechtes Beispiel für das Unterrichten von Rekursion sind - fast alle Demo-Implementierungen, die Sie in Tutorials oder Büchern finden, sind für große Eingabewerte unbrauchbar.)

Wenn Sie den Ablauf der Ausführung verfolgen, werden Sie feststellen, dass im zweiten Fall der Wert für fib ximmer verfügbar fib x+1ist, wenn er ausgeführt wird, und das Laufzeitsystem kann ihn einfach aus dem Speicher lesen und nicht über einen anderen rekursiven Aufruf, während der Die erste Lösung versucht, die größere Lösung zu berechnen, bevor die Ergebnisse für kleinere Werte verfügbar sind. Dies liegt letztendlich daran, dass der Iterator [0..n]von links nach rechts ausgewertet wird und daher mit beginnt 0, während die Rekursion im ersten Beispiel mit beginnt nund erst dann nachfragt n-1. Dies führt zu den vielen, vielen unnötigen doppelten Funktionsaufrufen.