La paresse et la récursion de la queue à Haskell, pourquoi cela s’effondre-t-il?

Question

J'ai cette fonction assez simple pour calculer la moyenne des éléments d'une grande liste, en utilisant deux accumulateurs pour contenir la somme jusqu'à présent et le compte 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 un langage strict, cela serait récursif et il n’y aurait pas de problème. Cependant, comme Haskell est paresseux, ma recherche sur Google m'a permis de comprendre que (s + x) et (l + 1) seront transmises à la récursion sous forme de thunks. Donc, tout cela se bloque et brûle:

Stack space overflow: current size 8388608 bytes.

Après une recherche approfondie, j'ai trouvé seq et $! . Cela me semble incompréhensible car toutes mes tentatives d'utilisation dans ce contexte se sont révélées vaines, les messages d'erreur indiquant quelque chose à propos de types infinis.

Enfin, j'ai trouvé -XBangPatterns , qui résout tout en modifiant l'appel récursif:

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

Mais cela ne me convient pas, car -XBangPatterns est actuellement une extension. J'aimerais savoir comment rendre l'évaluation stricte sans l'utilisation de -XBangPatterns . (Et peut-être apprendre quelque chose aussi!)

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

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

D'après ce que j'ai pu 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

J'ai beaucoup écrit à ce sujet:

• Monde réel Haskell, chapitre 24: contrôle de l'évaluation
• Récursivité et rigueur dans Haskell

Premièrement, oui, si vous souhaitez exiger une évaluation stricte des accumulateurs, utilisez seq et restez 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 de rigueur débutera si vous donnez des annotations de type et que vous compilez 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

Etant donné que 'Double' recouvre le type atomique strict Double #, avec des optimisations et un type précis, GHC exécute une analyse de rigueur et en 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 précédent sur RWH.

Answer 2

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

Habituellement, cela est lié au lien suivant:

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

Ceci est une variation 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 évalue en premier: seq est appelé avec les paramètres non encore é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 tente réellement d'accéder à leurs valeurs.

Maintenant, seq peut forcer l'évaluation de son premier paramètre avant de renvoyer le reste de l'expression. Ensuite, l'étape suivante de l'évaluation serait le deuxième seq . Si les appels à seq sont enterrés quelque part dans un paramètre, ils risquent de ne pas être exécutés pendant une longue période, ce qui compromettrait leur fonction.

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

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

Answer 3

Vous avez bien compris que seq s (s + x) force l'évaluation de s . Mais cela ne force pas s + x , vous construisez donc toujours des thunks.

En utilisant $! , vous pouvez forcer l'évaluation de l'addition (deux fois, pour les deux arguments). Cela produit le même effet que l’utilisation des motifs 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 $! traduira le go $! (s + x) à l'équivalent de:

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

Ainsi, y est d'abord forcé dans la forme normale de la tête faible , 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é en tant que 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. J'ai eu la même erreur quand j'ai écrit votre programme pour la première fois: -)

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