60
Was ist Haskells Stream Fusion und wie benutze ich es?Was ist Haskell's Stream Fusion
A
Antwort
60
Das Papier, auf das Logan zeigt, ist großartig, aber es ist ein wenig schwierig. (Fragen Sie einfach meine Schüler.) Es ist auch eine Menge darüber, "wie Strom Fusion funktioniert" und nur ein Bruchteil "was Strom Fusion ist und wie Sie es verwenden können".
Das Problem, das Fusion Stream löst, ist, dass funktionelle Codes oft geschrieben Zwischenlisten zuordnen, zum Beispiel eine unendliche Liste von Knotennummern zu erstellen, können Sie
nodenames = map ("n"++) $ map show [1..]
Naive Code schreiben würde eine unendliche Liste von zuteilen Ganzzahlen [1, 2, 3, ...], eine unendliche Liste von Strings ["1", "2", "3", ...], und schließlich eine unendliche Liste von Namen ["n1", "n2", "n3", ...]. Das ist zu viel Zuteilung.
Was Stream-Fusion tut, ist eine Definition wie nodenames in etwas übersetzen, die eine rekursive Funktion verwendet, die nur das zuweist, was für das Ergebnis benötigt wird. Im Allgemeinen wird die Eliminierung der Zuweisung von Zwischenlisten Entwaldung genannt.
verwenden Stream-Fusion, müssen Sie nicht-rekursive Liste Funktionen, die die Funktionen aus der Stream-Fusionsbibliothek in GHC ticket 915 (map, foldr, usw.) anstelle von expliziter Rekursion beschrieben verwenden zu schreiben. Diese Bibliothek enthält neue Versionen aller Prelude-Funktionen, die neu geschrieben wurden, um die Stream-Fusion auszunutzen. Offensichtlich ist dieses Zeug dazu gedacht, es in die nächste GHC-Version (6.12) zu bringen, ist aber nicht in der aktuellen stabilen Version (6.10). Wenn Sie die Bibliothek verwenden möchten, hat Porges eine schöne einfache Erklärung in seiner Antwort.
Wenn Sie eigentlich eine Erklärung wollen, wie Stream Fusion funktioniert, schreiben Sie eine andere Frage - aber das ist viel schwieriger.
+6
Gibt es Pläne, dies zum Standardverhalten der Auftaktliste zu machen? –
+1
Gibt es einen Unterschied in der Verschmelzung zwischen der Anwendung '$' und der Komposition '.'? – CMCDragonkai
+1
Sind Preludes Funktionen irgendwie markiert oder was? I.e. Warum funktioniert es nicht für eine selbstgemachte rekursive Funktion? –
12
Soweit ich weiß, und im Gegensatz zu dem, was Norman sagte, Stream Fusion ist nicht derzeit in GHC Basis implementiert (dh. Sie können nicht einfach Prelude Funktionen verwenden). Weitere Informationen finden Sie unter GHC ticket 915.
Um die Stream-Fusion zu verwenden, müssen Sie die stream-fusion-Bibliothek installieren, Data.List.Stream importieren (Sie können auch Control.Monad.Stream importieren) und nur Funktionen aus diesem Modul anstelle der Prelude-Funktionen verwenden. Dies bedeutet, dass das Prelude importiert wird, indem alle Standardlistenfunktionen ausgeblendet werden und keine [x..y] -Konstrukte oder Listenverstehen verwendet werden.
-1
Ist es nicht richtig, dass, wenn GHC in 6.12 diese neuen Funktionen standardmäßig verwendet, sie auch [x..y] implementieren und Comprehensions in dieser nicht-rekursiven Weise auflisten? Weil der einzige Grund, warum sie nicht die richtige Zeile sind, ist, dass sie intern sind und nicht wirklich in Haskell geschrieben sind, sondern eher wie Keywords, um der Geschwindigkeit willen und/oder weil Sie diese Syntax nicht neu definieren könnten.
Gibt es etwas, was Sie wissen müssen, das ist nicht bereits in [diesem Beitrag] (http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance) Kartenfusion: Haskell 225% schneller machen ")? Wenn ja, können Sie genauer sein? –
Related: http://lambda.jstolarek.com/2013/04/haskell-as-fast-as-ca-case-study/ –
Hinweis: Es gibt auch etwas namens List Fusion, die automatisch mit vielen gebauten geschieht in Funktionen: https://downloads.haskell.org/~ghc/7.4.2/docs/html/users_guide/rewrite-rules.html#id690070 und siehe http: // gewissenhafterProgrammierer.com/blog/2015/12/19/24-tage-von-hackage-2015-tag-19-ghc-core-html-liste-fusion-probe-checking-ghcs-fusion-umschreiben-regeln-für-löschen- intermediate-data-from-existess/wie überprüft man, ob es benutzt wird (oder versuche 'stack build --ghc-options" -ddump-rule-firings -ddump-rule-rewrites "&& find .stack-work/-name '* dump-rule *' '). – unhammer