Produit scalaire pour les listes dans Haskell

Question

J'essaie d'implémenter un produit scalaire entre deux listes de nombres en utilisant uniquement des fonctions de la bibliothèque Prelude. J'ai écrit la fonction suivante:

dot :: Num a => [a] -> [a] -> a 
dot x y = sum $ zipWith (*) x y 

que je l'ai testé comme suit:

main :: IO() 
main = do 
    let n = 10^6 
     x = (replicate n 2.0) :: [Double] 
     y = (replicate n 3.0) :: [Double] 
    print $ dot x y 
    return() 

Malheureusement, ce code conduit à un dépassement de l'espace de pile pour les listes avec 1 million d'éléments (à l'aide GHC 7.6. 3 et le drapeau d'optimisation -O2).

Pour un cas aussi simple, je m'attendais à ce que ghc puisse effectuer les optimisations nécessaires pour éviter le coût des appels récursifs. Est-ce que je manque quelque chose? Ma mise en œuvre est-elle incorrecte?

Answer 1

sum est (mis en œuvre) avec foldr. C'est un peu un choix bête pour plus instances de Num; un pli gauche strict est préférable. À la place, le débordement de pile disparaîtra.