Dépassement de pile dans GHCI lorsque vous tentez d'afficher un nombre

Question

En essayant d'apprendre Haskell, j'ai implémenté un calcul de pi afin de comprendre correctement les fonctions et la récursivité.

Utilisation du Leibniz Formula pour calculer pi, je suis venu avec ce qui suit, qui imprime pi à la tolérance du paramètre donné, et le nombre de fonction récursive appels afin d'obtenir cette valeur:

reverseSign :: (Fractional a, Ord a) => a -> a 
reverseSign num = ((if num > 0 
         then -1 
         else 1) * (abs(num) + 2)) 

piCalc :: (Fractional a, Integral b, Ord a) => a -> (a, b) 
piCalc tolerance = piCalc' 1 0.0 tolerance 0 

piCalc' :: (Ord a, Fractional a, Integral b) => a -> a -> a -> b -> (a, b) 
piCalc' denom prevPi tolerance count = if abs(newPi - prevPi) < tolerance 
             then (newPi, count) 
             else piCalc' (reverseSign denom) newPi tolerance (count + 1) 
             where newPi = prevPi + (4/denom) 

Alors, quand je lance cela dans GHCi, il semble fonctionner comme prévu:

*Main> piCalc 0.001 
(3.1420924036835256,2000) 

Mais si je mets ma tolérance trop fine, cela se produit:

*Main> piCalc 0.0000001 
(3.1415927035898146,*** Exception: stack overflow 

Cela me semble totalement contre-intuitif; le calcul réel fonctionne bien, mais juste en essayant d'imprimer combien d'appels récursifs échoue ??

Pourquoi est-ce ainsi?

Answer 1

Ceci est une variante du débordement de pile traditionnel foldl (+) 0 [1..1000000]. Le problème est que la valeur de comptage n'est jamais évaluée lors de l'évaluation de piCalc'. Cela signifie qu'il porte juste un ensemble croissant de thunks représentant l'addition à faire si nécessaire. Quand cela est nécessaire, le fait que l'évaluer nécessite une profondeur de pile proportionnelle au nombre de thunks provoque le débordement.

La solution la plus simple utilise l'extension BangPatterns, en changeant le début de piCalc' à

piCalc' denom prevPi tolerance !count = ... 

Cela force la valeur de count à évaluer lorsque le motif est mis en correspondance, ce qui signifie qu'il ne se développera jamais une chaîne géante de thunks.

Équivalemment, et sans l'utilisation d'une extension, vous pouvez l'écrire comme

piCalc' denom prevPi tolerance count = count `seq` ... 

C'est exactement équivalent sémantiquement à la solution ci-dessus, mais il utilise seq explicitement au lieu de implicitement via une extension du langage. Cela le rend plus portable, mais un peu plus verbeux.

Quant à savoir pourquoi l'approximation de pi n'est pas une longue séquence de thunks imbriquées, mais le nombre est: piCalc' branches sur le résultat d'un calcul qui nécessite les valeurs de newPi, prevPi et tolerance.Il doit examiner ces valeurs avant de décider si cela est fait ou s'il doit exécuter une autre itération. C'est cette branche qui provoque l'exécution de l'évaluation (lorsque l'application de la fonction est effectuée, ce qui signifie généralement que quelque chose correspond au résultat de la fonction.) En revanche, rien dans le calcul de piCalc' ne dépend de la valeur de count, il n'est donc pas évalué pendant le calcul.

Answer 2

Le compte n'est jamais évalué pendant le calcul, il est donc laissé comme une énorme quantité de thunk (débordant la pile) jusqu'à la fin.

Vous pouvez forcer son évaluation au cours du calcul en permettant l'extension et de l'écriture BangPatternspiCalc' denom prevPi tolerance !count = ...

Alors pourquoi nous ne devons forcer l'évaluation des count? Eh bien, tous les autres arguments sont évalués dans le if. Nous devons en fait tous les inspecter avant d'appeler à nouveau le piCalc', de sorte que les thunks ne s'accumulent pas; nous avons besoin des valeurs réelles, pas seulement des «promesses qu'ils peuvent être calculées»! count, d'autre part, n'est jamais nécessaire pendant le calcul, et peut rester comme une série de thunk jusqu'à la toute fin.