Ich las das Haskell-Prelude und fand es ziemlich verständlich, dann stolperte ich über die Definition der Exponentiation:
%Vor% Ich verstehe die Notwendigkeit von zwei verschachtelten where s nicht.
Was ich bisher verstanden habe:
%Vor%Die Basis muss eine Zahl sein und der Exponent intege, ok.
%Vor%Basisfall, einfach.
%Vor% Exponention durch Quadrieren ... Art von ... Warum wird der f Helfer benötigt? Warum sind f und g mit einem Buchstaben versehen? Ist es nur Optimierung, vermisse ich etwas Offensichtliches?
N & gt; 0 wurde vorher überprüft, N ist negativ, wenn wir hier ankommen, also Fehler.
Meine Implementierung wäre eine direkte Übersetzung von:
%Vor%Pseudocode aus Wikipedia.
Um zu verdeutlichen, was @dfeuer sagt, beachte, dass die Art f es entweder geschrieben hat:
f gibt einen Wert f ruft sich selbst mit neuen Argumenten Daher ist f tail rekursiv und kann daher leicht in eine Schleife umgewandelt werden.
Betrachten Sie andererseits diese alternative Implementierung der Potenzierung durch Quadrieren:
%Vor% Das Problem hierbei ist, dass in der anderen Klausel die letzte durchgeführte Operation eine Multiplikation ist. Also exp entweder:
x . exp ist nicht tail rekursiv und kann daher nicht in eine Schleife umgewandelt werden.
f ist in der Tat eine Optimierung. Der naive Ansatz wäre "von oben nach unten", berechnet x^(n 'div' 2) und quadriert dann das Ergebnis. Der Nachteil dieses Ansatzes besteht darin, dass er einen Stapel von Zwischenberechnungen aufbaut. Was f diese Implementierung tun lässt, ist das erste Quadrat x (eine einzelne Multiplikation) und hebt dann das Ergebnis auf den reduzierten Exponenten, Tail rekursiv, an. Das Endergebnis ist, dass die Funktion wahrscheinlich vollständig in Maschinenregistern arbeitet. g scheint zu vermeiden, das Ende der Schleife zu prüfen, wenn der Exponent gerade ist, aber ich bin mir nicht sicher, ob es eine gute Idee ist.
Soweit ich es verstehe, wird die Potenzierung durch Quadrieren gelöst, solange der Exponent gerade ist.
Dies führt zu der Antwort, warum f im Falle einer ungeraden Zahl benötigt wird - wir verwenden f , um das Ergebnis im Fall von g x 1 zurückzugeben, in jedem anderen ungeraden Fall verwenden wir f zurück in der g -Routine.
Sie können es am besten sehen, wenn Sie sich ein Beispiel ansehen:
%Vor%Nun zu Ihrer Frage, einzelne Buchstabenfunktionsnamen zu verwenden - daran müssen Sie sich erst gewöhnen, schreiben die meisten Leute in der Community. Es hat keine Auswirkungen auf den Compiler, wie Sie Ihre Funktionen benennen - solange sie mit einem Kleinbuchstaben beginnen.
Wie bereits erwähnt, wird die Funktion aus Effizienzgründen mit Tail-Recursion geschrieben.
Beachten Sie jedoch, dass Sie das innerste where entfernen können, während Sie die Schwanzrekursion wie folgt beibehalten: statt
können wir verwenden
%Vor%was auch besser lesbar ist.
Ich habe jedoch keine Ahnung, warum die Autoren des Preludes ihre Variante gewählt haben.
Tags und Links haskell functional-programming haskell-prelude