Laziness und Endrekursion in Haskell, warum ist das abstürzt?

Question

Ich habe diese ziemlich einfache Funktion den Mittelwert der Elemente einer großen Liste zu berechnen, unter Verwendung von zwei Akkumulatoren die Summe so weit und die Zählung so weit zu halten:

mean = go 0 0
    where
      go s l []     = s / fromIntegral l
      go s l (x:xs) = go (s+x) (l+1) xs

main = do
  putStrLn (show (mean [0..10000000]))

Nun, in einer strengen Sprache, dies wäre Schwanz-rekursiv, und es wäre kein Problem. Doch wie Haskell faul ist, mein Googeln hat mich dazu gebracht, dass (n + x) und (l + 1) wird überliefert die Rekursion als Thunks zu verstehen. Also diese ganze Sache Abstürze und Verbrennungen:

Stack space overflow: current size 8388608 bytes.

Nach weiteren Googeln fand ich seq und $!. Welche es scheint, ich verstehe nicht, weil alle meine Versuche, mit ihnen in diesem Zusammenhang vergeblich erwiesen, mit Fehlermeldungen sagen etwas über unendliche Arten.

Schließlich fand ich -XBangPatterns, die sie alle durch eine Änderung der rekursiven Aufruf löst:

go !s !l (x:xs) = go (s+x) (l+1) xs

Aber ich bin damit nicht glücklich, als -XBangPatterns derzeit eine Erweiterung ist. Ich würde gerne wissen, wie die Auswertung streng ohne die Verwendung von -XBangPatterns zu machen. (Und vielleicht etwas lernen!)

Nur damit Sie meinen Mangel an Verständnis zu verstehen, hier ist, was ich versucht (die nur versuchen, die kompiliert, das ist):

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs

Von dem, was ich verstehen konnte, seq sollte hier zwingen, die Bewertung des s und l Arguments, wodurch das Problem vermieden durch Thunks verursacht. Aber ich immer noch einen Stapelüberlauf.

Answer 1

Ich habe ausführlich über diese geschrieben:

• Real World Haskell, ch 24: Steuern Auswertung
• auf Rekursion und Strikt in Haskell

Zum einen ja, wenn Sie wollen strenge Bewertung der Akkumulatoren seq verwenden verlangen und den Aufenthalt in Haskell 98:

mean = go 0 0
  where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = s `seq` l `seq`
                      go (s+x) (l+1) xs

main = print $ mean [0..10000000]

*Main> main
5000000.0

Zweitens: Strenge Analyse treten, wenn Sie irgendeine Art Anmerkungen geben, und kompiliert mit -O2:

mean :: [Double] -> Double
mean = go 0 0
 where
  go :: Double -> Int -> [Double] -> Double
  go s l []     = s / fromIntegral l
  go s l (x:xs) = go (s+x) (l+1) xs

main = print $ mean [0..10000000]

$ ghc -O2 --make A.hs
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.0
./A  0.46s user 0.01s system 99% cpu 0.470 total

Weil ‚Double‘ ist ein Wrapper über die strengen Atomtyp Doppel #, mit Optimierungen auf, und einer präzisen Art, GHC läuft Strenge Analyse und folgert, dass die strenge Version ok sein wird.

import Data.Array.Vector

main = print (mean (enumFromToFracU 1 10000000))

data Pair = Pair !Int !Double

mean :: UArr Double -> Double   
mean xs = s / fromIntegral n
  where
    Pair n s       = foldlU k (Pair 0 0) xs
    k (Pair n s) x = Pair (n+1) (s+x)

$ ghc -O2 --make A.hs -funbox-strict-fields
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.5
./A  0.03s user 0.00s system 96% cpu 0.038 total

Wie oben im RWH Kapitel beschrieben.

Answer 2

Die seq Funktion Kräfte Auswertung des ersten Parameters, sobald die Funktion aufgerufen wird. Wenn Sie seq s (s+x) als Parameter die seq Funktion übergeben ist nicht sofort angerufen, weil es keine Notwendigkeit gibt, den Wert dieses Parameters zu bewerten. Sie wollen, dass der Anruf an seq vor dem rekursiven Aufruf ausgewertet werden, so dass dieser wiederum seine Parameter ausgewertet werden erzwingen.

In der Regel wird dies geschehen Link folgt aus:

 go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs

Dies ist eine syntaktische Variante von seq s (seq l (go (s+x) (l+1) xs)). Hier werden die Anrufe an seq sind die äußersten Funktionsaufrufe in den Ausdruck ein. Wegen Haskells Faulheit dies bewirkt, dass sie zuerst ausgewertet werden. seq mit dem noch nicht ausgewerteten Parametern s und seq l (go (s+x) (l+1) xs) genannt wird, die Parameter der Bewertung zu dem Punkt verschoben wird, wo jemand tatsächlich versucht, ihre Werte zugreifen

Jetzt kann seq erste Parameter erzwingen vor der Rückkehr in den Rest des Ausdrucks ausgewertet werden. Dann ist der nächste Schritt in der Bewertung wäre die zweite seq sein. Wenn die Anrufe an seq sind irgendwo in einem Parameter begraben könnten sie nicht für eine lange Zeit ausgeführt werden, ihren Zweck zu besiegen.

Mit den veränderten Positionen der seqs das Programm fein ausgeführt wird, ohne übermäßige Mengen an Speicher.

Eine andere Lösung für das Problem wäre, einfach Optimierungen in GHC zu aktivieren, wenn das Programm kompiliert wird (-O oder -O2). Der Optimierer erkennt die entbehrlichen Faulheit und erzeugt Code, der nicht unnötig Speicher zuordnet.

Answer 3

Sie haben Recht in Ihrem Verständnis, dass zwingt die Auswertung von seq s (s+x) s. Aber es funktioniert nicht s+x zwingen, deshalb bist du noch Thunks aufzubauen.

Durch die Verwendung von $! Sie die Auswertung der Zugabe zwingen kann (zweimal, für beide Argumente). Dadurch wird erreicht, die gleiche Wirkung wie das Knall-Muster mit:

mean = go 0 0
 where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = ((go $! s+x) $! l+1) xs

---

Die Verwendung der $! Funktion wird den go $! (s+x) auf die äquivalent übersetzen:

let y = s+x 
in seq y (go y)

So wird y erste gezwungen, in schwachen Kopf Normalform , was bedeutet, dass die äußerste Funktion angewandt wird. Im Fall von y ist die äußerste Funktion + wird somit y vollständig auf eine Zahl ausgewertet, bevor go geleitet wird.

---

Oh, und Sie wahrscheinlich die unendliche Typ Fehlermeldung bekommen, weil Sie nicht die Klammern an der richtigen Stelle haben. Ich habe den gleichen Fehler, wenn ich zum ersten Mal das Programm nach unten schrieb: -)

Da der $! Operator rechts assoziativ ist, ohne Klammer go $! (s+x) $! (l+1) bedeutet das gleiche wie:. go $! ((s+x) $! (l+1)), was offensichtlich falsch ist