Ich schrieb last function mit foldl1 und foldr1 .
Sie funktionieren nur gut für kurze Listen. Aber als ich mit einer sehr langen Liste versuchte, [1..10 ^ 8], gibt Lastr die Lösung in 6,94 Sekunden zurück, aber der letzte Speicher ist leer.
Definition von foldr1 und foldl1 sind (nach meinem Verständnis)
%Vor%und
%Vor% Daraus ergibt sich, dass folll1 weniger Speicher als foldr1 benötigt, weil foldr1 einen Ausdruck wie f x1 $ f x2 $ f x3 $ f x4 $... behalten muss, während foldl1 immer f x y jedes Mal berechnen und als Kopfelement einer Liste speichern kann, anstatt es zu halten bis es zu 10 ^ 8 kommt.
Könnte mir jemand sagen, was mit meinem Argument nicht stimmt?
Die rechte Falte kann sofort produzieren, wenn die Kombinationsfunktion in ihrem zweiten Argument faul ist. Ein einfaches Beispiel:
%Vor% und der erste Teil des Ergebnisses ist sofort zugänglich, ohne das zweite Argument von (++) weiter zu bewerten. Dies muss nur ausgewertet werden, wenn der erste Teil verbraucht ist. Oft kann der erste Teil dann schon Müll gesammelt werden.
Im Beispiel mit f = flip const als kombinierender Funktion haben wir eine andere Situation, das heißt strikt (1) in seinem zweiten Argument, muss es aber überhaupt nicht auswerten. Und es ignoriert sein erstes. Das ist auch gut für rechte Falten. Hier geht es
und jetzt kann das äußerste f sofort ausgewertet werden
und bei jedem Schritt kann das äußerste f immer sofort (vollständig) ausgewertet und ein Listenelement weggeworfen werden.
Wenn die Liste von einem Generator gegeben wird, der sie beim sequentiellen Verbrauch in konstantem Raum erzeugen kann,
%Vor%kann in konstantem Speicherplatz ausgeführt werden.
Mit der linken Falte sind die Dinge anders. Da ist das Tail-rekursive
%Vor%es kann nichts zurückgeben, bevor die Falte das Ende der Liste erreicht hat. Insbesondere kann eine linke Falte niemals auf einer unendlichen Liste enden.
Wenn wir nun unseren Fall f = flip const betrachten, finden wir
Natürlich wäre es möglich, sofort f x1 x2 auf x2 und dann f x2 x3 = x3 auszuwerten, aber das ist nur für diese spezielle f möglich.
Da foldl eine allgemeine Funktion höherer Ordnung ist, kann sie die Zwischenergebnisse nicht vor dem Bedarf auswerten, da die Zwischenergebnisse möglicherweise niemals benötigt werden - und tatsächlich werden sie am Ende nie benötigt von der Liste bekommt man einen Ausdruck
und dann kann das äußerste f ausgewertet werden, ohne auf den riesigen Thunk der verschachtelten f s zu schauen, der das erste Argument erzeugt.
foldl (bzw. foldl1 ) kann nicht wissen, dass es viel effizienter gewesen wäre, die Zwischenergebnisse sofort auszuwerten.
Die strengen linken Falten, foldl' und foldl1' machen das, sie bewerten die Zwischenergebnisse als schwache Kopfnormalform (zum äußersten Wertkonstruktor oder Lambda) und
wäre auch sehr effizient.
Da die Zwischenergebnisse jedoch weiter ausgewertet werden als mit foldr , wären sie ein wenig weniger effizient und, wenn ein Listenelement ⊥ ist, würde die foldl1' Version ⊥ zurückgeben:
wobei die foldr1 Version kein Problem damit hat, da sie die Listenelemente oder Zwischenergebnisse überhaupt nicht überprüft.
(1) Das f ist streng in seinem zweiten Argument bedeutet das
Da f einfach das zweite Argument zurückgibt, ist das offensichtlich der Fall.
Tags und Links haskell