comment résoudre « débordement de l'espace de pile » dans haskell

Question

L'exécution du programme suivant imprimera « débordement de l'espace: la taille actuelle 8388608 octets. » J'ai lu cette et cette , mais ne savent toujours pas comment résoudre mon problème. J'utilise foldr, il ne devrait pas être garantie « queue récursive »?

Je me sens bien à propos de Haskell jusqu'à jusqu'à ce que je sais que je devrais éviter « débordement de l'espace » lors de l'utilisation du puissant récursivité. :)

module Main where
import Data.List

value a  b = 
  let l = length $ takeWhile (isPrime) $ map (\n->n^2 + a * n + b) [0..]
  in (l, a ,b)

euler27 = let tuple_list = [value a b | a <-[-999..999] , b <- [-999..999]]
      in foldr (\(n,a,b) (max,v) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list
main = print euler27

EDIT: supprimer le definiton de isPrime pour la simplicité

Answer 1

Comme réponse Pierr, vous devez utiliser foldl'. Pour plus de détails:

• foldl' calcule son « côté gauche » avant de le donner à votre étape de pliage.
• foldr donne à votre étape de fois un « thunk » pour la valeur du côté droit. Ce « thunk » sera calculé en cas de besoin.

Faisons une somme avec foldr et voir comment il évalue:

foldr (+) 0 [1..3]
1 + foldr (+) 0 [2..3]
1 + 2 + foldr (+) 0 [3]
1 + 2 + 3 + foldl (+) 0 [] -- this is a big thunk..
1 + 2 + 3 + 0
1 + 2 + 3
1 + 5
6

Et avec foldl': (balise omise dans le code parce que SO ne l'affiche pas bien)

foldl (+) 0 [1..3]
-- seq is a "strictness hint".
-- here it means that x is calculated before the foldl
x `seq` foldl (+) x [2..3] where x = 0+1
foldl (+) 1 [2..3]
x `seq` foldl (+) x [3] where x = 1+2
foldl (+) 3 [3]
x `seq` foldl (+) x [] where x = 3+3
foldl (+) 6 []
6

Dans de bonnes utilisations pour foldr, qui ne fuit pas. la "étape" doit:

• Retourne un résultat qui ne dépend pas du « côté droit », en ignorant ou en contenant dans une structure paresseuse
• Retour le côté droit comme il est

Des exemples de bon usage de foldr:

-- in map, the step returns the structure head
-- without evaluating the "right-side"
map f = foldr ((:) . f) []

filter f =
  foldr step []
  where
    step x rest
      | f x = x : rest -- returns structure head
      | otherwise = rest -- returns right-side as is

any f =
  foldr step False
  where
    -- can use "step x rest = f x || rest". it is the same.
    -- version below used for verbosity
    step x rest
      | f x = True -- ignore right-side
      | otherwise = rest -- returns right-side as is

Answer 2

remplacer

foldr (\(n,a,b) (max,v) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list

avec

foldl' (\(max ,v) (n,a,b) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list

résolu ce problème, devrait suggérer que nous devrions toujours préférer utiliser foldl » au lieu d'autres variantes (foldl, foldr)?