La paresse et la récursivité de la queue chez Haskell, pourquoi est ce crash?

Question

Je cette fonction assez simple pour calculer la moyenne des éléments d'une grande liste, en utilisant deux accumulateurs pour maintenir la somme à ce jour et le nombre jusqu'à présent:

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])) 

Maintenant, dans une langue stricte, ce serait être récursif à la queue, et il n'y aurait pas de problème. Cependant, comme Haskell est paresseux, mon googling m'a amené à comprendre que (s + x) et (l + 1) seront transmis la récursion comme thunks. Donc, ce ça plante et brûlures:

Stack space overflow: current size 8388608 bytes. 

Après plus googler, je trouve seq et $!. Ce qu'il semble que je ne comprends pas parce que toutes mes tentatives pour les utiliser dans ce contexte se sont révélées vaines, avec des messages d'erreur disant quelque chose à propos des types infinis.

Enfin, je trouve -XBangPatterns, qu'il résout tout en changeant l'appel récursif:

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

Mais je ne suis pas content de cela, comme -XBangPatterns est actuellement une extension. Je voudrais savoir comment rendre l'évaluation stricte sans l'utilisation de -XBangPatterns. (! Et peut-être apprendre quelque chose de trop)

que vous compreniez bien mon manque de compréhension, voici ce que j'ai essayé (le seul essai que compilé, c'est):

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

D'après ce que je pouvais comprendre, seq devrait ici forcer l'évaluation de l'argument s et l, évitant ainsi le problème causé par les thunks. Mais j'ai toujours un débordement de pile.

Answer 1

Je l'ai écrit sur ceci:

• Real World Haskell, ch 24: controlling evaluation
• On recursion and strictness in Haskell

Tout d'abord, oui, si vous voulez exiger une évaluation stricte des accumulateurs utilisent seq et de rester dans 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 

Deuxièmement: l'analyse rigueur donnera le coup si vous donnez des annotations de type, et compiler avec -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 

Parce que « Double » est une enveloppe sur la stricte de type atomique Double #, avec des optimisations sur, et précise type, GHC exécute une analyse de rigueur et déduit que la version stricte sera correcte.

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 

Comme décrit dans le chapitre RWH ci-dessus.

Answer 2

Vous avez raison dans votre compréhension que seq s (s+x) force l'évaluation de s. Mais cela ne force pas s+x, donc vous construisez toujours des thunk. En utilisant $!, vous pouvez forcer l'évaluation de l'addition (deux fois, pour les deux arguments) en utilisant .Cela permet d'atteindre le même effet que les modèles bang:

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

---

L'utilisation de la fonction $! traduirons le go $! (s+x) à l'équivalent de:

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

Ainsi y est d'abord forcé dans faible forme normale de la tête, ce qui signifie que la fonction la plus externe est appliquée. Dans le cas de y, la fonction la plus externe est +, ainsi y est entièrement évalué à un nombre avant d'être passé à go. Oh, et vous avez probablement reçu le message d'erreur de type infini parce que vous n'aviez pas la parenthèse au bon endroit. Je suis la même erreur quand j'écrit votre programme vers le bas :-)

Parce que l'opérateur $! est associative droite, sans parenthèses go $! (s+x) $! (l+1) signifie la même chose que: go $! ((s+x) $! (l+1)), ce qui est évidemment faux.

Answer 3

La fonction seq force l'évaluation du premier paramètre une fois la fonction appelée. Lorsque vous passez seq s (s+x) comme paramètre, la fonction seq est et non appelée immédiatement, car il n'est pas nécessaire d'évaluer la valeur de ce paramètre. Vous voulez que l'appel à seq soit évalué avant l'appel récursif, afin que cela puisse à son tour forcer l'évaluation de son paramètre.

Habituellement, cela se fait lien ceci:

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

Ceci est une variante syntaxique de seq s (seq l (go (s+x) (l+1) xs)). Ici, les appels à seq sont les appels de fonction les plus externes dans l'expression. En raison de la paresse de Haskell, cela les fait d'abord évaluer: seq est appelé avec les paramètres encore non évalués s et seq l (go (s+x) (l+1) xs), l'évaluation des paramètres est différée au point où quelqu'un essaie réellement d'accéder à leurs valeurs.

Maintenant, seq peut forcer son premier paramètre à être évalué avant de renvoyer le reste de l'expression. Ensuite, la prochaine étape de l'évaluation serait la deuxième seq. Si les appels à seq sont enterrés quelque part dans un paramètre, ils pourraient ne pas être exécutés pendant une longue période, en vainant leur but.

Avec les positions modifiées du seq, le programme s'exécute correctement, sans utiliser de quantité excessive de mémoire.

Une autre solution au problème serait de simplement activer les optimisations dans GHC lors de la compilation du programme (-O ou -O2). L'optimiseur reconnaît la paresse dispensable et produit un code qui n'alloue pas de mémoire inutile.