Ich habe gerade Haskell vor zwei Tagen angefangen, also bin ich mir noch nicht sicher, wie ich meinen Code optimieren soll.
Als Übung habe ich foldl und foldr neu geschrieben (ich gebe foldl hier, aber foldr ist gleich, ersetze last mit head und init mit tail ) .
Der Code lautet:
%Vor%Meine einzige Sorge ist, dass ich vermute, dass Haskell hier keine Tail-Call-Optimierung anwenden kann, weil der rekursive Aufruf nicht am Ende der Funktion erfolgt.
Wie kann ich diesen Tail Call optimieren? Ist Haskells eingebaute Implementierung von foldl anders implementiert als meine?
Ihre Verwendung von Klammern in Ihrem Codebeispiel und Ihre Betonung der Tail-Rekursion legen nahe, dass Sie von Lisp oder Scheme zu Haskell kommen. Wenn Sie von einer eifrigen Sprache wie Scheme nach Haskell kommen, seien Sie gewarnt: Tail-Calls sind bei Haskell nicht annähernd so leistungsfähig wie in einer eifrigen Sprache. Sie können tail-recursive Funktionen haben, die wegen Faulheit im linearen Raum ausgeführt werden, und können nicht-tail-rekursive Funktionen haben, die wegen Faulheit im konstanten Raum ausgeführt werden. (Schon verwirrt?)
Erster Fehler in deiner Definition ist die Verwendung von length theList == 0 . Dies erzwingt die Auswertung der gesamten Wirbelsäule der Liste und ist O (n) Zeit. Es ist besser, den Mustervergleich zu verwenden, wie in dieser naiven foldl -Definition in Haskell:
Dies ist jedoch in Haskell sehr schlecht, weil wir den f z x -Teil nicht berechnen, bis der Aufrufer von foldl das Ergebnis verlangt; Also akkumuliert diese foldl nicht bewertete Thunks im Speicher für jedes Listenelement und hat keinen Vorteil davon, tail rekursiv zu sein. Tatsächlich kann dieses naive foldl über eine lange Liste hinweg zu einem Stapelüberlauf führen, obwohl es tailrekursiv ist! (Das Modul Data.List hat eine foldl' -Funktion das hat dieses Problem nicht.)
Im Gegensatz dazu funktionieren viele rekursive Haskell-Nicht-Tail-Funktionen sehr gut. Nehmen wir zum Beispiel diese Definition von find , basierend auf der zugehörigen nicht-tail-rekursiven Definition von foldr :
Dies wird tatsächlich in linearer Zeit und konstantem Raum ausgeführt, dank Faulheit. Warum?
rest zu berechnen. Die Lektion, die ich jetzt vermitteln möchte, lautet: Bringen Sie Ihre Leistungsannahmen aus eifrigen Sprachen nicht in Haskell ein. Du bist nur zwei Tage drin; Konzentriere dich zuerst darauf, die Syntax und Semantik der Sprache zu verstehen, und verzichte nicht darauf, bereits optimierte Funktionen zu schreiben. Du wirst von Zeit zu Zeit von Zeit zu Zeit mit dem foldl -Style-Stack-Overflow konfrontiert werden, aber du wirst es rechtzeitig meistern.
EDIT [9/5/2012]: Einfachere Demonstration, dass lazy find in konstantem Raum läuft, obwohl sie nicht tail rekursiv ist. Erstens, vereinfachte Definitionen:
Nun, unter Verwendung von Gleichungsberechnungen (d. h. Ersetzen von Gleichem mit Gleichem basierend auf der obigen Definition) und Auswerten in einer faulen Reihenfolge (äußerste zuerst), berechnen wir find (==400) [1..] :
Beachten Sie, dass die Ausdrücke in den aufeinanderfolgenden Bewertungsschritten im Verlauf der Liste nicht immer komplexer oder länger werden; die Länge oder Tiefe des Ausdrucks in Schritt n ist nicht proportional zu n , es ist im Wesentlichen fest. Dies zeigt in der Tat, wie find (==400) [1..] im konstanten Raum träge ausgeführt werden kann.
Idiomatisch Haskell sieht sehr anders aus, vermeidet wenn-dann-sonst, verschachtelte Lambdas, Klammern und Destrukturierungsfunktionen (Kopf, Schwanz). Stattdessen würden Sie etwas schreiben wie:
%Vor%Stattdessen wird beim Mustervergleich eine where-Klausel, eine Tail-Rekursion und geschützte Deklarationen verwendet.
Tags und Links haskell tail-call-optimization