3

キックのために、Haskell で関数を として定義するとどうなるかを確認したかったのですが、Int -> Intオーバーフローして を返さなければならないことがわかっていIntegerます。次の点を考慮してください。

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

factorial 50これで、 を実行すると、 の「コドメイン」外の数値が取得されることがわかりましたfactorial。Haskell は非常に厳密に型付けされているため、エラーが返されることを期待していました。代わりに GHCi は奇妙な負の値を返しますInt:

ghci> factorial 50
-3258495067890909184

そして、それに注意してください

ghci> maxBound :: Int
9223372036854775808

私は64ビットで実行しているので。

Haskell がエラーを発生させないのはなぜですか? そして、なぜfactorial 50ランダムな負の数を返すのですか? 明確化をいただければ幸いです。

4

1 に答える 1

20

型は、Int「少なくとも範囲 [-2^29 .. 2^29-1] の固定精度整数型」として定義されます。minBound[0] 範囲はマシンによって異なりますが、とで見つけることができます。maxBound

オーバーフローする理由は、固定量のメモリが割り当てられているためです。より単純な例を想像してみてください。最大値が 7 であるメモリ内の正の整数 (メモリ内に 3 ビットとして格納されます)

0 は 000 として表され、バイナリで
は 1 は 001 として
表され、2 は 010 として表されます。

ビット演算の仕組みに注意してください: 1 を追加すると、最小の桁を 0 から 1 に変更するか、1 から 0 に変更して次の最上位桁で同じ操作を行います。

たとえば、011 + 1は100です。

次の最上位桁がないときに単純に (Haskell のように) これを実行すると、通常どおりインクリメントされますが、「頭が切れる」ことになります。たとえば、 の代わりに111 + 1なります。これは Haskell で起こっていることです。0001000その最小値 (一連の として表される0) は、最小の負の数です。「一番左」のビットを使用して +/- を表します。(maxBound :: Int) + (maxBound :: Int) + 20 を取得するために行う必要があります。

同様に：

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

なぜこれが起こるのを「許可」するのですか？シンプル - 効率。整数オーバーフローが発生するかどうかをチェックしない方がはるかに高速です。これが存在する理由Integerです。オーバーフローする可能性があると思われる場合は無制限ですが、効率の代償を払うことになります。

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

于 2013-07-20T20:53:14.713 に答える