Ich bin nur neugierig, ob es (nur polymorphe Optimierung erster Ordnung) Optimierungen mit Falten gibt.
Für Karten gibt es Abholzung: map g (map f ls) => map (g . f) ls und rev (map f ls) => rev_map f ls (schneller in Ocaml).
Aber Fold ist so mächtig, es scheint sich jeder Optimierung zu widersetzen.
Die offensichtlichen:
%Vor%Vielleicht interessieren Sie sich für die klassische Arbeit zum Thema "Funktionale Programmierung mit Bananen, Linsen, Umschlägen und Stacheldraht". Beachten Sie jedoch, dass es technisch ist und undurchdringliche Notation hat.
Bearbeiten: meine erste Version der ersten Regel war falsch, editiert dank vincent-hugot.
Sie können Abholzung auf Falten verwenden. Tatsächlich ist map/map fusion ein Sonderfall.
Der Trick besteht darin, die Listenkonstruktion durch eine spezielle Funktion build zu ersetzen:
Verwenden Sie nun die Standarddefinition von foldr
Wir haben folgende Äquivalenz:
%Vor%(Dies trifft nur unter bestimmten, aber üblichen Umständen zu. Details finden Sie unter "Korrektheit der Abkürzung" ).
Wenn Sie Ihre Listenerstellungsfunktionen (einschließlich map ) mit build und Ihre Konsumenten mit foldr schreiben, kann die obige Gleichheit die meisten Zwischenlisten entfernen. Haskells Listenkompressen werden in Kombinationen von build und foldr übersetzt.
Der Nachteil dieses Ansatzes ist, dass er nicht mit linken Falten umgehen kann. Stream Fusion erledigt dies jedoch gut. Es drückt Listenproduzenten und Transformatoren als Ströme aus (koinduktive Datentypen, eine Art von Iteratoren). Das obige Papier ist sehr gut lesbar, daher empfehle ich einen Blick darauf.
Das von ganche erwähnte "Bananen" -Papier geht näher auf Faltenarten und ihre Äquivalenzen ein.
Schließlich gibt es Bird and Moors "Algebra of Programming" , die erwähnt Transformationen wie die Kombination von zwei Falten zu einem .
Wenn Sie interessiert sind, ein wenig tiefer in die Theorie zu gehen, schlage ich vor, dass Sie etwas über Katamorphismen lesen, Anamorphismen und Hylomorphismen . Während die Kategorientheorie, die sie umgibt, etwas gruselig erscheinen mag, ist das Konzept nicht so schwierig.
Katamorphismen sind Funktionen, die rekursive Datenstrukturen konsumieren und eine Art von Wert erzeugen. Anamorphismen sind Funktionen, die durch einen bestimmten Wert (eine Art Seed) rekursive Datenstrukturen erzeugen. Insbesondere foldr und build , die in den anderen Antworten erwähnt werden, sind Funktionen zum Aufbau von Katamorphismen und Anamorphismen auf Listen. Dieses Konzept kann jedoch grundsätzlich auf jede rekursive Datenstruktur angewendet werden, wie z. B. verschiedene Arten von Bäumen usw.
Wenn Sie nun eine rekursive Datenstruktur mit einem Anamorphismus erstellen und diese dann mit einem Katamorphismus konsumieren, erhalten Sie einen sogenannten Hylomorphismus. In einem solchen Fall benötigen Sie die Zwischenstruktur eigentlich nicht. Sie können überspringen, es zu erstellen und zu zerstören. Dies wird oft Abholzung genannt.
Betreffend map : Diese Funktion ist interessant, dass es sich sowohl um einen Katamorphismus als auch um einen Anamorphismus handelt:
map verbraucht eine Liste und erzeugt etwas; aber auch map erzeugt eine Liste, die etwas verbraucht. Sie können also die Zusammensetzung von zwei Maps map f . map g als eine Zusammensetzung eines Anamorphismus ( map g ) mit einem Katamorphismus ( map f ) betrachten und einen Hylomorphismus bilden. Sie wissen also, dass Sie die Zwischenliste optimieren können, indem Sie sie nicht erstellen.
Um genau zu sein: Sie könnten map auf zwei Arten schreiben, eine mit foldr und die andere mit build :
und die Zusammensetzung map f (map g zs) als mapCata f (mapAna g zs) , was nach einigen Vereinfachungen und Anwendung von foldr c n (build g) == g c n in map (f . g) resultiert.
Tags und Links performance functional-programming ocaml fold