La paresse et la récursion de la queue à Haskell, pourquoi cela s’effondre-t-il?
-
06-07-2019 - |
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.
La solution
J'ai beaucoup écrit à ce sujet:
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.
Autres conseils
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.
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.