Ich versuche Haskell zu lernen und ich stolperte über Folgendes:
%Vor%Beim Kompilieren mit GHC ergibt dies einen Stapelüberlauf. Als C / C ++ - Programmierer hätte ich erwartet, dass der Compiler die Tail Call-Optimierung durchführt.
Ich mag es nicht, dass ich den Compiler in einfachen Fällen wie diesen "unterstützen" müsste, aber welche Möglichkeiten gibt es? Ich denke, es ist vernünftig zu verlangen, dass die obige Berechnung ohne Verwendung von O (n) -Speicher und ohne Verzögerung auf spezielle Funktionen durchgeführt wird.
Wenn ich mein Problem natürlich nicht erklären kann (selbst bei einem Spielzeugproblem wie diesem), erwarte ich eine angemessene Leistung in Bezug auf die Zeit & amp; Raum würde viel von der Attraktivität von Haskell verloren gehen.
Stelle zuerst sicher, dass du mit -O2 kompilierst. Es macht eine Menge Leistungsprobleme einfach weg:)
Das erste Problem, das ich sehen kann, ist, dass null nur ein Variablenname ist. Du willst [] . Dies ist hier gleichbedeutend, da die einzigen Optionen x:xs und [] sind, aber nicht immer.
Das Problem hier ist einfach: Wenn Sie sum [1,2,3,4] aufrufen, sieht das so aus:
, ohne jemals irgendwelche dieser Zusätze zu einer Zahl zu reduzieren, wegen Haskells nicht-strikter Semantik. Die Lösung ist einfach:
%Vor% (Sie benötigen {-# LANGUAGE BangPatterns #-} am Anfang Ihrer Quelldatei, um dies zu kompilieren.)
Dies akkumuliert die Addition in einem anderen Parameter und ist tatsächlich tail rekursiv (deins ist nicht; + ist in der Tail-Position und nicht myAdd ). Aber in Wirklichkeit ist es nicht die Tail-Rekursion, die uns in Haskell interessiert; diese Unterscheidung ist hauptsächlich in strengen Sprachen relevant. Das Geheimnis ist hier das bang Muster auf total : es zwingt es jedes Mal, wenn myAdd' aufgerufen wird, auszuwerten, so dass keine unevaluierten Additionen aufgebaut werden, und es läuft im konstanten Raum. In diesem Fall kann GHC dies dank seiner Striktheitsanalyse tatsächlich mit -O2 herausfinden, aber ich denke, es ist normalerweise am besten, explizit darüber zu sein, was genau Sie wollen und was nicht.
Beachten Sie, dass Ihre myAdd -Definition gut funktionieren würde, wenn die Addition faul wäre; Das Problem ist, dass Sie eine faule Durchsuchung der Liste mit einer strict -Operation durchführen, die letztendlich den Stack-Überlauf verursacht. Dies ergibt sich hauptsächlich aus Arithmetik, die für die numerischen Standardtypen (Int, Integer, Float, Double usw.) streng ist.
Das ist ziemlich hässlich, und es wäre ein Schmerz, wenn wir jedesmal etwas schreiben würden, wenn wir eine strikte Falte schreiben wollen. Zum Glück hat Haskell eine Abstraktion dafür bereit!
%Vor% (Sie müssen import Data.List hinzufügen, um dies zu kompilieren.)
foldl' (+) 0 [a, b, c, d] ist genau wie (((0 + a) + b) + c) + d , außer dass bei jeder Anwendung von (+) (so wird der binäre Operator + als Funktionswert bezeichnet) der Wert gezwungen ausgewertet zu werden. Der resultierende Code ist sauberer, schneller und einfacher zu lesen (sobald Sie wissen, wie die Liste klappt, können Sie jede Definition verstehen, die einfacher geschrieben ist als eine rekursive Definition).
Im Grunde ist das Problem hier nicht, dass der Compiler nicht herausfinden kann, wie man sein Programm effizient macht - es kann so effizient sein, wie man möchte seine Semantik ändern , was eine Optimierung sein sollte Tue niemals. Haskells nicht-strikte Semantik stellt Programmierern sicherlich eine Lernkurve in "traditionelleren" Sprachen wie C zur Verfügung, aber es wird mit der Zeit einfacher und sobald Sie die Macht und Abstraktion sehen, die Haskells Nicht-Strenge bietet, werden Sie nie mehr gehen wollen zurück:)
Erweitern Sie das Beispiel, das in den Kommentaren angedeutet wurde:
%Vor% result ist True durch die Definition von myAdd , aber wenn der Compiler in eine tail-rekursive Schleife umgewandelt wird, würde er nicht enden. Diese Transformation ist also nicht nur eine Veränderung in der Effizienz, sondern auch in der Semantik, daher muss ein Compiler das nicht tun
Ein lustiges Beispiel in Bezug auf "Das Problem ist, warum der Compiler nicht in der Lage ist, etwas zu optimieren, das zur Optimierung eher trivial erscheint."
Sagen wir, ich komme von Haskell nach C ++. Ich habe foldr geschrieben, weil in Haskell foldr wegen Faulheit und Listenfusion normalerweise effektiver ist als foldl .
Also versuche ich ein foldr für eine (single-linked) Liste in C zu schreiben und beschwerde mich, warum es grob ineffizient ist:
Es ist ineffizient, nicht weil der betreffende C-Compiler ein unrealistisches Spielzeugwerkzeug ist, das von Theoretikern im Elfenbeinturm zu ihrer eigenen Zufriedenheit entwickelt wurde, sondern weil der fragliche Code für C völlig unwichtig ist.
Es ist nicht so, dass Sie in C kein effizientes foldr schreiben können: Sie brauchen nur eine doppelt verknüpfte Liste. In Haskell können Sie ähnlich eine effiziente foldl schreiben, Sie benötigen Striktheitsannotationen für foldl , um effizient zu sein. Die Standardbibliothek bietet sowohl foldl (ohne Annotationen) als auch foldl' (mit Annotationen).
Die Idee, eine Liste in Haskell nach links zu falten, ist die gleiche Art von Perversion wie der Wunsch, eine einfach verknüpfte Liste rückwärts zu rekursiv in C zu kompilieren. Compiler soll normalen Menschen helfen, nicht perversen lol.
Da Ihre C ++ - Projekte wahrscheinlich keinen Code haben, der einfach verknüpfte Listen rückwärts iteriert, enthält mein HNC-Projekt nur 1 foldl , das ich falsch geschrieben habe, bevor ich Haskell genug beherrschte. Sie müssen fast nie foldl in Haskell.
Sie müssen verlernen, dass die Vorwärtsiteration natürlich und am schnellsten ist, und lernen, dass die Rückwärtsiteration ist. Die Vorwärts-Iteration (Linke Faltung) macht nicht das, was Sie beabsichtigen, bis Sie kommentieren: Es gibt drei Durchgänge - Listenerstellung, Thunk-Kettenaufbau und Thunk-Auswertung statt zwei (Listenerstellung und Listendurchlauf). Beachten Sie, dass Listen in unveränderlichen Welt nur effizient rückwärts erstellt werden können: a: b ist O (1) und a ++ [b] ist O (N).
Und die Rückwärtsiteration macht auch nicht das, was Sie beabsichtigen. Es macht einen Durchlauf statt drei, wie Sie von Ihrem C-Hintergrund erwarten können. Es erstellt keine Liste, durchläuft sie nach unten und durchquert sie dann rückwärts (2 Durchläufe) - sie durchquert die Liste, wenn sie erstellt wird, dh 1 Durchlauf. Wenn Optimierungen aktiviert sind, handelt es sich nur um eine Schleife - es werden keine tatsächlichen Listenelemente erstellt. Bei deaktivierten Optimierungen ist es immer noch O (1) Space-Operation mit einem größeren konstanten Overhead, aber die Erklärung ist etwas länger.
Es gibt also zwei Dinge, die ich auf Ihr Problem ansprechen werde, erstens das Leistungsproblem und zweitens das expressive Problem, dem Compiler mit etwas zu helfen, das trivial erscheint.
Die Leistung
Die Sache ist, dass Ihr Programm tatsächlich nicht tail rekursiv ist, das heißt, es gibt keinen einzigen Aufruf an eine Funktion, die die Rekursion ersetzen kann. Werfen wir einen Blick darauf, was passiert, wenn wir myAdd [1..3] erweitern:
Wie Sie sehen können, können wir die Rekursion bei jedem Schritt nicht durch einen Funktionsaufruf ersetzen. Wir könnten den Ausdruck vereinfachen, indem wir 1 + 2 auf 3 reduzieren, aber darum geht es bei der Tail-Rekursion nicht.
Also hier ist eine Version, die tail rekursiv ist:
%Vor% Schauen wir uns an, wie go 0 [1,2,3] ausgewertet wird:
Wie Sie sehen, müssen wir bei jedem Schritt nur den Überblick behalten
ein Funktionsaufruf, und solange der erste Parameter ist
Streng ausgewertet sollten wir keinen exponentiellen Raum bekommen
sprengen, und in der Tat, wenn Sie mit der Optimierung kompilieren ( -O1 oder -O2 )
GhC ist schlau genug, um das herauszufinden.
Ausdruckskraft
Okay, es ist ein bisschen schwieriger, über die Leistung in Haskell nachzudenken, aber die meiste Zeit müssen Sie nicht. Die Sache ist, dass Sie Kombinatoren verwenden können, die Effizienz sicherstellen. Dieses spezielle obige Muster wird von foldl (und seinem strikten Cousin foldl' ) erfasst, so dass myAdd folgendermaßen geschrieben werden kann:
und wenn Sie das mit Optimierung kompilieren, wird es Ihnen keinen exponentiellen Raumauftrieb geben!