math - Haskell中整数的上限是多少？

Question

我正在解决一个数学问题:想要得到数字 2^1000 的数字总和。

在 Java 中，解决方案是这样的:

String temp = BigInteger.ONE.shiftLeft(1000).toString();

int sum = 0;
for (int i = 0; i < temp.length(); i++)
    sum += temp.charAt(i) - '0';

然后在 Haskell 中想出了一个解决方案，像这样:

digitSum ::(Integral a) => a -> a                  
digitSum 0 = 0
digitSum n = (mod n 10) + (digitSum (div n 10))

整个过程还算顺利，有一点很有意思，我们知道整型不能处理2 ^ 1000，太大了，在Java中，显然用BigInteger 并将大数处理为字符串，但在 Haskell 中，没有编译错误意味着 2 ^ 1000 可以直接传入。问题是，Haskell 是否在内部将数字转换为字符串？我想确定类型是什么并让编译器确定，然后我在 GHCi 中键入以下行:

Prelude> let i = 2 ^ 1000

Prelude> i 
107150860718626732094842504906000181056140481170553360744375038837035105112493612249319
837881569585812759467291755314682518714528569231404359845775746985748039345677748242309
854210746050623711418779541821530464749835819412673987675591655439460770629145711964776
86542167660429831652624386837205668069376

Prelude> :t i
i :: Integer

到这里，我完全懵了，显然i的个数太大了，但是i的返回类型还是Integer。我们如何解释这个以及 Haskell 的 Integer 的上限或限制是多少？

Answer 1

在 Haskell 中，Integer 是一种 - 理论上 - 无界整数类型。固定宽度类型有 Int、Int8、Int16、Int32、Int64 和相应的无符号Word, Word8等

在实践中，甚至 Integer 当然也是有界的，例如受可用内存或内部表示的限制。

默认情况下，GHC 使用 GMP 包来表示 Integer，这意味着边界是 2^(2^37) 左右，因为 GMP 使用 32 - 位整数，用于存储肢体数量。