Traitement douteux de 'Int' et 'Integer' en Haskell ?

Question

Juste pour le plaisir, j'ai voulu voir ce qui se passerait si je définissais une fonction en Haskell de la manière suivante Int -> Int en sachant qu'il déborderait et devrait renvoyer un Integer . Considérons ce qui suit :

factorial :: Int -> Int
factorial n = product [1..n]

Maintenant je sais que si je cours factorial 50 je vais obtenir un numéro en dehors du "codomaine" de l'article. factorial . Puisque Haskell est si fortement typé, j'espérais qu'il renverrait une erreur. Au lieu de cela, GHCi renvoie un étrange négatif Int :

ghci> factorial 50
-3258495067890909184

Et notez que

ghci> maxBound :: Int
9223372036854775808

puisque je fonctionne en 64 bits.

Je trouve ce comportement plutôt effrayant : pourquoi Haskell ne lève-t-il pas une erreur ? Et pourquoi factorial 50 retourner un nombre négatif aléatoire ? Toute clarification serait grandement appréciée.

Answer 1

El Int type est défini comme "Un type d'entier à précision fixe avec au moins l'intervalle [-2^29 .. 2^29-1]". [0] L'intervalle varie selon la machine mais vous pouvez le trouver avec minBound y maxBound

La raison pour laquelle il déborde est qu'une quantité fixe de mémoire lui est allouée. Imaginez un exemple plus simple : un nombre entier positif en mémoire dont la valeur maximale est 7 (stocké sur 3 bits en mémoire).

0 est représenté par 000, en binaire
1 est représenté par 001
2 est représenté par 010, etc.

Notez comment fonctionne le calcul des bits : lorsque vous ajoutez 1, vous faites passer le plus petit chiffre de 0 à 1, ou vous le faites passer de 1 à 0 et vous effectuez la même opération sur le chiffre le plus significatif suivant.

Donc, par exemple, 011 + 1 es 100 .

Maintenant, si vous faites naïvement (comme le fait Haskell) cette opération quand il y a pas de le chiffre le plus significatif suivant, alors il incrémente comme d'habitude, mais "se fait couper la tête". Par exemple 111 + 1 devient 000 au lieu de 1000 . C'est ce qui se passe avec Haskell, sauf que sa valeur la plus basse (représentée par une série de 0 s) est son plus petit nombre négatif. il utilise son bit le plus à gauche pour représenter +/-. Vous devrez faire (maxBound :: Int) + (maxBound :: Int) + 2 pour obtenir 0.

De la même façon :

>  maxBound :: Int  
9223372036854775807  
>  (maxBound :: Int) + 1  
-9223372036854775808  
>  (maxBound :: Int) + 2  
-9223372036854775807  
>  let x = (maxBound :: Int) + 1 in x + x
0

Pourquoi "permettre" que cela se produise ? C'est simple : l'efficacité. Il est beaucoup plus rapide de ne pas vérifier s'il y aura un débordement d'entier. C'est la raison pour laquelle Integer existe - elle n'est pas bornée, pour les cas où vous pensez que vous pourriez déborder, mais vous payez le prix de l'efficacité.

[0] http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Int.html