Memoization in Haskell

Kann mir jemand die folgende Funktion erklären?

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)

(Code vom Haskell-Wiki)

Kellerautomat

Was genau verstehst du nicht? Verstehst du nicht, wie die Funktion die Werte berechnet, oder was hier als Memoization bezeichnet wird?

Ich dachte, Haskell hätte einen GC, der alle ungebrauchten Objekte verwirft. Aber scheinbar wird die Liste im Speicher gehalten. Ist das irgendwie geregelt oder verlässt man sich da auf einen guten Compiler oder was ist das los

Kellerautomat

Gleich vorweg, ich habe den Artikel selbst zum ersten mal gelesen, also keine 100%-ige Garantie, dass das stimmt. Ich habe es so verstanden, dass fuer jeden Aufruf von memoized_fib die Ergebnisse von fib zwischengespeichert werden. Sprich: Die Werte werden bei jedem Aufruf von memoized_fib neu berechnet, aber nicht bei jedem Aufruf von fib.

Kannst du das genauer erläutern? Haskell ist ja lazy, d.h.

memoized_fib n

hat erstmals keinen Wert.
Was passiert also bei der Auswertung? Mit !! wird nun auf das nte Element zugegriffen.

map fib [0..] !! n

Die Liste ist ja non-strict und sieht damit erst einmal so aus:

fib 0 : fib 1 : fib 2 : fib 3 : fib 4 : fib 5 : fib 6 : ... : fib n : ...

Also gibt !!n den lazy Ausdruck fib n zurück, der Aufruf von memoized_fib ist schon längst "verlassen".

Man könnte also schreiben

memoized_fib = fib

... und dann hätte man wieder die langsame Implementation ohne Memoization. Wo ist der Denkfehler?

Kellerautomat

Irgendwo hast du Recht. Zuerst hab ich geglaubt, es verstanden zu haben, aber mittlerweile bin ich mir da nicht mehr so sicher.

nachtfeuer

Schreib doch einfach mal die genannten Funktionen und Abläufe jeweils im Vergleich in Einzelschritten auf.

Das hilft dem Verständnis oft sehr gut auf die Sprünge, wie halt beim Austüfteln von Algorithmen mit Bleistift und Papier.

Und wie weit kommst du bei der Fibonacci-Berechnung im Kopf?

nachtfeuer schrieb:

Schreib doch einfach mal die genannten Funktionen und Abläufe jeweils im Vergleich in Einzelschritten auf.

Hab ich im oberen Post versucht. Das Ergebnis ist das richtige, nicht aber die Laufzeitkomplexität.

Kannst du meinen Denkfehler aufzeigen?

knivil

(map fib [0 ..] !!)

Das ist deine Closure. Sie besitzt intern eine lazy Liste mit alle Fibonacci-Zahlen. Elemente die bis dahin noch nicht benoetigt wurden, sind auch noch nicht berechnet. Prinzipiell eine unendliche Datenstruktur mit einer Indirektion.

Etwas einfacher ohne Indirektion:

ones ::[Integer]
ones = 1:ones

Um das Beispiel zu verstehen, muss lazyness, closures und unendlich Datenstrukturen verstanden sein.

Bashar

knivil schrieb:

(map fib [0 ..] !!)
Das ist deine Closure. Sie besitzt intern eine lazy Liste mit alle Fibonacci-Zahlen. Elemente die bis dahin noch nicht benoetigt wurden, sind auch noch nicht berechnet. Prinzipiell eine unendliche Datenstruktur mit einer Indirektion.

Ich glaub das hat hier jeder verstanden. Die Frage war, warum die schon berechneten Ergebnisse der Liste behalten werden, so dass man den Memoization-Effekt hat, und nicht einfach weggeworfen und bei Bedarf neu berechnet werden.

knivil

Genau deswegen:

memoized_fib = (map fib [0 ..] !!)

Mal in der Sprache C++. memoized_fib als globaler Funktionszeiger zeigt auf den Funktor (map fib [0 ..] !!) . Das ist ein Objekt. Also warum geht dieser Funktor/Objekt nicht einfach nach dem Aufruf weg? Na weil der globale Zeiger memoized_fib immernoch drauf zeigt und das Objekt demnach nicht vom Garbage collector abgeraeumt wird.

Zeus

knivil schrieb:

Genau deswegen:
memoized_fib = (map fib [0 ..] !!)
Mal in der Sprache C++. memoized_fib als globaler Funktionszeiger zeigt auf den Funktor (map fib [0 ..] !!) . Das ist ein Objekt. Also warum geht dieser Funktor/Objekt nicht einfach nach dem Aufruf weg? Na weil der globale Zeiger memoized_fib immernoch drauf zeigt und das Objekt demnach nicht vom Garbage collector abgeraeumt wird.

Ist das wirklich global, ich hätte gedacht, dass der Zeiger/Reference bist zum Call Site propagiert wird.

knivil

dass der Zeiger/Reference bist zum Call Site propagiert wird.

Kannst du das naeher ausfuehren, ich Weiss nicht wie und was du damit meinst.

Zeus

knivil schrieb:

dass der Zeiger/Reference bist zum Call Site propagiert wird.

Kannst du das naeher ausfuehren, ich Weiss nicht wie und was du damit meinst.

Eigentlich intressiert mich, ob Haskell das nun wirklich global anlegt oder auch kürzere Lebenszeiten gibt. Unter der JVM würden indirekte Referenze langen. fib und memoized_fib sind "Funktoren", während memoized_fib noch die Map referenziert. Solange der Aufrufer die Referenz von memoized_fib hat, lebt auch das Closure-Objekt,d.h. es könnte Garbage werden, wenn der Stack abgearbeitet wurde.

Es scheint tatsächlich am Closure zu liegen.

closureless_fib :: Int -> Integer
closureless_fib = \n -> map fib [0 ..] !! n
  where fib 0 = 0
        fib 1 = 1
        fib n = closureless_fib (n-2) + closureless_fib (n-1)

Dieser Code ist enorm langsam.

Die explizit memoizierte Variante ist dagegen wieder schnell:

yetanother_fib :: Int -> Integer
yetanother_fib = make_use_of table
 where table = map fib [0 ..]
       make_use_of dat n = dat !! n
       fib 0 = 0
       fib 1 = 1
       fib n = yetanother_fib (n-2) + yetanother_fib (n-1)

Es geht also darum, die Daten in einer partiell angewendeten Funktion zu speichern.

Jetzt verstehe ich auch die Wiki-Seite besser. Danke knivil!

knivil

Solange der Aufrufer die Referenz von memoized_fib hat, lebt auch das Closure-Objekt,d.h. es könnte Garbage werden, wenn der Stack abgearbeitet wurde.

Die Referenz ist global, genau wie in C beispielsweise jede Funktion. Sie wird einmal bei Programmstart angelegt.