Verschachtelung Listenfunktionen

Question

Lets sagen, dass ich zwei Funktionen gegeben habe:

f :: [a] -> b 
g :: [a] -> c 

ich eine Funktion schreiben wollen, die das Äquivalent davon ist:

h x = (f x, g x) 

Aber wenn ich das tue, für große Listen zwangsläufig ich nicht mehr genügend Speicher.

Ein einfaches Beispiel ist die folgende:

x = [1..100000000::Int] 
main = print $ (sum x, product x) 

Ich verstehe dies der Fall ist, weil die Liste x wird, ohne Müll gesammelt im Speicher abgelegt werden. Es wäre besser, statt f und g auf x in, naja, "parallel" gearbeitet.

Angenommen, ich nicht f ändern und g, noch will eine separate Kopie von x machen (unter der Annahme x ist teuer in der Herstellung), wie kann ich h schreiben, ohne Probleme aus dem Speicher läuft in?

Answer 1

Sie können mehrere Threads verwenden, um f x und g x parallel auszuwerten.

z.

x :: [Int] 
x = [1..10^8] 

main = print $ let a = sum x 
        b = product x 
       in a `par` b `pseq` (a,b) 

Es ist eine gute Möglichkeit, die parallele Laufzeit von GHC auszunutzen, um ein Platzleck zu verhindern, indem zwei Dinge gleichzeitig ausgeführt werden.

Alternativ müssen Sie f und g in a single pass fusionieren.

Answer 2

Eine kurze Antwort ist, können Sie nicht. Da Sie keine Kontrolle über f und g haben, können Sie nicht garantieren, dass die Funktionen ihre Eingaben sequentiell verarbeiten. Eine solche Funktion kann auch die gesamte Liste im Speicher behalten, bevor das Endergebnis erzeugt wird.

Wenn jedoch Ihre Funktionen als Falten ausgedrückt werden, ist die Situation anders. Dies bedeutet, dass wir jeden Schritt schrittweise anwenden können, sodass wir diese Schritte in einem Durchgang parallelisieren können.

Das sind viele Ressourcen zu diesem Bereich. Zum Beispiel:

• Haskell: Can I perform several folds over the same lazy list without keeping list in memory?
• Klassischen Beautiful folding
• More beautiful fold zipping

---

das Muster eine Folge von Werten mit richtig definierten Raum Grenzen des Verzehrs wird allgemein mit rohrartigen Bibliotheken gelöst so Leitung, iterates o r Rohre.Zum Beispiel in Leitung, könnten Sie die Kombination von Rechen Summen und Produkten wie

import Control.Monad.Identity 
import Data.Conduit 
import Data.Conduit.List (fold, sourceList) 
import Data.Conduit.Internal (zipSinks) 

product', sum' :: (Monad m, Num a) => Sink a m a 
sum'  = fold (+) 0 
product' = fold (*) 1 

main = print . runIdentity $ sourceList (replicate (10^6) 1) $$ 
           zipSinks sum' product' 

Answer 3

Express Wenn Sie Ihre Funktionen in Falten drehen können, kann man sich dann nur mit einem Scan verwenden:

x = [1..100000000::Int] 
main = mapM_ print . tail . scanl foo (a0,b0) . takeWhile (not.null) 
     . unfoldr (Just . splitAt 1000) -- adjust the chunk length as needed 
     $ x 

foo (a,b) x = let a2 = f' a $ f x ; b2 = g' b $ g x 
       in a2 `seq` b2 `seq` (a2, b2) 

f :: [t] -> a   -- e.g. sum 
g :: [t] -> b   --  (`rem` 10007) . product 
f' :: a -> a -> a  -- e.g. (+) 
g' :: b -> b -> b  --  ((`rem` 10007) .) . (*) 

wir verbrauchen die Eingabe in Chunks für eine bessere Leistung. Zusammen mit -O2 sollte dies in einem konstanten Raum ausgeführt werden. Die Zwischenergebnisse werden als Fortschrittsanzeige gedruckt.

Wenn Sie Ihre Funktion nicht in eine Falte umwandeln können, bedeutet dies, dass hat, um die gesamte Liste zu konsumieren, um irgendeine Ausgabe zu produzieren, und dieser Trick trifft nicht zu.