Wie wird diese Fibonacci-Funktion gespeichert?

Durch welchen Mechanismus wird diese Fibonacci-Funktion gespeichert?

fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

Und in einem ähnlichen Zusammenhang, warum ist diese Version nicht?

fib n = (map fib' [0..] !! n)                                               
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

Der Bewertungsmechanismus in Haskell ist bedarfsgerecht : Wenn ein Wert benötigt wird, wird er berechnet und für den Fall, dass er erneut angefordert wird, bereitgehalten. Wenn wir eine Liste definieren xs=[0..]und später nach ihrem 100. Element fragen, xs!!99wird der 100. Platz in der Liste "konkretisiert", wobei die Nummer 99jetzt für den nächsten Zugriff bereitgehalten wird.

Das ist es, was dieser Trick, "eine Liste durchgehen", ausnutzt. Bei der normalen doppelt rekursiven Fibonacci-Definition wird fib n = fib (n-1) + fib (n-2)die Funktion selbst zweimal von oben aufgerufen, was die exponentielle Explosion verursacht. Aber mit diesem Trick erstellen wir eine Liste für die Zwischenergebnisse und gehen "durch die Liste":

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

Der Trick besteht darin, dass diese Liste erstellt wird und diese Liste zwischen den Aufrufen von nicht (durch Speicherbereinigung) verschwindet fib. Der einfachste Weg, dies zu erreichen, besteht darin , diese Liste zu benennen . "Wenn du es nennst, wird es bleiben."

Ihre erste Version definiert eine monomorphe Konstante und die zweite eine polymorphe Funktion. Eine polymorphe Funktion kann nicht dieselbe interne Liste für verschiedene Typen verwenden, die sie möglicherweise bereitstellen muss, also keine Freigabe , dh keine Memoisierung.

Mit der ersten Version ist der Compiler großzügig mit uns, nimmt diesen konstanten Unterausdruck ( map fib' [0..]) heraus und macht ihn zu einer separaten gemeinsam nutzbaren Einheit, ist jedoch nicht dazu verpflichtet. ^{und es gibt tatsächlich Fälle, in denen wir nicht möchten, dass dies automatisch für uns erledigt wird.}

( bearbeiten :) Betrachten Sie diese Umschreibungen:

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

Die eigentliche Geschichte scheint also von den verschachtelten Bereichsdefinitionen zu handeln. Bei der 1. Definition gibt es keinen äußeren Bereich, und bei der dritten Definition wird darauf geachtet, nicht den äußeren Bereich fib3, sondern dieselbe Ebene zu nennen f.

Jeder neue Aufruf von fib2scheint seine verschachtelten Definitionen neu zu erstellen, da jeder von ihnen (theoretisch) je nach Wert von unterschiedlich definiert werden könnte (danke an Vitus und Tikhon für den Hinweis). Bei der ersten Definition gibt es keine Abhängigkeit, und bei der dritten gibt es eine Abhängigkeit, aber bei jedem einzelnen Aufruf von Aufrufen wird darauf geachtet, nur Definitionen aus demselben Bereich aufzurufen, die für diesen spezifischen Aufruf von intern sind , damit dasselbe erreicht wird für diesen Aufruf von wiederverwendet (dh geteilt) .nnfib3ffib3xsfib3

Nichts hindert den Compiler jedoch daran zu erkennen, dass die internen Definitionen in einer der obigen Versionen tatsächlich unabhängig von der äußeren nBindung sind, um schließlich das Lambda-Heben durchzuführen , was zu einer vollständigen Memoisierung führt (mit Ausnahme der polymorphen Definitionen). Genau das passiert bei allen drei Versionen, wenn sie mit monomorphen Typen deklariert und mit dem Flag -O2 kompiliert werden. Zeigt bei polymorphen Typdeklarationen fib3lokale Freigabe und überhaupt fib2keine Freigabe.

Abhängig von einem Compiler und den verwendeten Compiler-Optimierungen und wie Sie ihn testen (Laden von Dateien in GHCI, kompiliert oder nicht, mit -O2 oder nicht oder eigenständig) und ob es sich um einen monomorphen oder einen polymorphen Typ handelt, kann das Verhalten letztendlich sein Vollständige Änderung - ob lokale (pro Anruf) gemeinsame Nutzung (dh lineare Zeit bei jedem Anruf), Memoisierung (dh lineare Zeit beim ersten Anruf und 0-mal bei nachfolgenden Anrufen mit demselben oder einem kleineren Argument) oder überhaupt keine gemeinsame Nutzung ( exponentielle Zeit).

Die kurze Antwort lautet: Es ist eine Compilersache. :) :)

Ich bin nicht ganz sicher, aber hier ist eine fundierte Vermutung:

Der Compiler geht davon aus, dass fib ndies bei einem anderen unterschiedlich sein könnte, nund müsste daher die Liste jedes Mal neu berechnen. Die Bits in der whereAnweisung könnten schließlich davon abhängen n. Das heißt, in diesem Fall ist die gesamte Liste der Zahlen im Wesentlichen eine Funktion von n.

Die Version ohne n kann die Liste einmal erstellen und in eine Funktion einschließen. Die Liste kann nicht vom Wert der nübergebenen Liste abhängen und ist leicht zu überprüfen. Die Liste ist eine Konstante, in die dann indiziert wird. Es ist natürlich eine Konstante, die träge ausgewertet wird, sodass Ihr Programm nicht versucht, die gesamte (unendliche) Liste sofort abzurufen. Da es sich um eine Konstante handelt, kann sie von allen Funktionsaufrufen gemeinsam genutzt werden.

Es wird überhaupt gespeichert, weil der rekursive Aufruf nur einen Wert in einer Liste nachschlagen muss. Da die fibVersion die Liste einmal träge erstellt, berechnet sie gerade genug, um die Antwort zu erhalten, ohne redundante Berechnungen durchzuführen. Hier bedeutet "faul", dass jeder Eintrag in der Liste ein Thunk ist (ein nicht bewerteter Ausdruck). Wenn Sie den Thunk auswerten, wird er zu einem Wert. Wenn Sie also das nächste Mal darauf zugreifen, wird die Berechnung nicht wiederholt. Da die Liste von Anrufen gemeinsam genutzt werden kann, werden alle vorherigen Einträge bereits zum Zeitpunkt berechnet, zu dem Sie den nächsten benötigen.

Es ist im Wesentlichen eine clevere und kostengünstige Form der dynamischen Programmierung, die auf der faulen Semantik von GHC basiert. Ich denke, der Standard legt nur fest, dass er nicht streng sein muss , sodass ein kompatibler Compiler diesen Code möglicherweise kompilieren kann, um ihn nicht zu speichern. In der Praxis wird jedoch jeder vernünftige Compiler faul sein.

Weitere Informationen darüber, warum der zweite Fall überhaupt funktioniert, finden Sie unter Grundlegendes zu einer rekursiv definierten Liste (Fibs in Bezug auf zipWith) .

Erstens ist mit ghc-7.4.2, kompiliert mit -O2, die nicht gespeicherte Version nicht so schlecht, die interne Liste der Fibonacci-Nummern wird immer noch für jeden Aufruf der Funktion auf oberster Ebene gespeichert. Es ist jedoch nicht und kann nicht vernünftigerweise über verschiedene Anrufe der obersten Ebene hinweg gespeichert werden. Bei der anderen Version wird die Liste jedoch von mehreren Anrufen gemeinsam genutzt.

Das liegt an der Monomorphismusbeschränkung.

Die erste ist an eine einfache Musterbindung gebunden (nur der Name, keine Argumente), daher muss sie durch die Monomorphismusbeschränkung einen monomorphen Typ erhalten. Der abgeleitete Typ ist

fib :: (Num n) => Int -> n

und eine solche Einschränkung wird standardmäßig (sofern keine Standarddeklaration etwas anderes sagt) auf festgelegt Integer, wobei der Typ als festgelegt wird

fib :: Int -> Integer

Somit gibt es nur eine Liste (vom Typ [Integer]), die gespeichert werden muss.

Das zweite wird mit einem Funktionsargument definiert, bleibt also polymorph, und wenn die internen Listen über Aufrufe hinweg gespeichert würden, müsste für jeden Typ in eine Liste gespeichert werden Num. Das ist nicht praktisch.

Kompilieren Sie beide Versionen mit deaktivierter Monomorphismus-Einschränkung oder mit identischen Typensignaturen, und beide zeigen genau das gleiche Verhalten. (Das galt nicht für ältere Compilerversionen, ich weiß nicht, welche Version es zuerst getan hat.)

Sie benötigen keine Memoize-Funktion für Haskell. Nur empirische Programmiersprachen benötigen diese Funktionen. Haskel ist jedoch funktional lang und ...

Dies ist also ein Beispiel für einen sehr schnellen Fibonacci-Algorithmus:

fib = zipWith (+) (0:(1:fib)) (1:fib)

zipWith ist eine Funktion aus dem Standard-Präludium:

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

Prüfung:

print $ take 100 fib

Ausgabe:

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]

Verstrichene Zeit: 0,00018s