Wie kann ich zwei Karten über dieselbe Liste verschmelzen? automatisch

Question

Wir verschmelzen können zwei Überquerungen über die Liste xs im Ausdruck

(map f xs, map g xs) 

wie so

unzip (map (\x -> (f x, g x)) xs) 

Gibt es eine reasearch auf diese Art von Fusion durchführen?

(Es gibt ein Risiko, hier einen Raum Leck zu schaffen, wenn eine der zurück Listen vor dem anderen verbraucht wird ich die zusätzliche Traversal über xs bei der Prävention als platzsparend mehr interessiert bin..)

Edit: Ich Ich versuche eigentlich nicht, die Fusion auf tatsächliche In-Memory-Haskell-Listen anzuwenden, wo diese Transformation keinen Sinn ergibt, je nachdem ob die unzip mit ihren Consumern verschmolzen werden kann. Ich habe eine Einstellung, wo ich weiß unzip kann fusionieren (siehe "FlumeJava: einfache, effiziente Daten-parallele Pipelines").

Answer 1

Auch nicht vollautomatisch, aber Sie können GHC eine Liste von Rewrite-Regeln wie diese geben. Siehe 7.14 Rewrite rules und Using rules. Dann verwendet der Compiler diese Regeln, um Ihr Programm beim Kompilieren zu optimieren. (Beachten Sie, dass der Compiler in keiner Weise überprüft, ob die Regeln keinen Sinn.)

Edit: ein Beispiel für dieses spezielle Problem zu geben, können wir schreiben:

{-# OPTIONS_GHC -fenable-rewrite-rules -ddump-rule-firings -ddump-rule-rewrites #-} 

import Data.Char 

{-# RULES 
"map/zip" forall f g xs. (,) (map f xs) (map g xs) = unzip (map (\x -> (f x, g x)) xs) 
    #-} 

main :: IO() 
main = let x = "abCD" in 
     print $ (,) (map toUpper x) (map toLower x) 

(das Top-Level Funktionsname in der Regel ist (,) :: a -> b -> (a, b)). Beim Kompilieren sehen Sie, wie die Regeln angewendet werden. Option dump-rule-firings zeigt eine Meldung an, wenn eine Regel angewendet wird, und -ddump-rule-rewrites zeigt jede Regelanwendung im Detail an - siehe 7.14.6. Controlling what's going on in rewrite rules.

Answer 2

Ich habe es geschafft, zwei Ressourcen zu finden, die Fusion (un-) zip wie Funktionen erwähnt, zumindest kurzzeitig:

Josef Svenningsson. "Shortcut Fusion für Akkumulationsparameter & Zip-ähnliche Funktionen" http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

Duncan Coutts. "Stream Fusion: Praktische Abkürzungsfusion für koinduktive Sequenztypen" https://community.haskell.org/~duncan/thesis.pdf

Keine der Ressourcen erwähnt diese Art von "Geschwisterfusion" jedoch explizit.