Haskell整数; 到底发生了什么？

Question

最近对Haskell感到好奇,我开始做一些阅读. Integer我在想我的想法.

当我们说a Integer可以任意大时,这是否意味着我认为它意味着什么(即a的大小Integer不受OS的地址宽度限制)？

假设我有足够的RAM可用于存放具有十亿个值的数字.Haskell能够使用这个数字吗？

任何人都可以向我描述一下有什么可能吗？

Answer 1

假设我有足够的RAM可用于存放具有十亿个值的数字.Haskell能够使用这个数字吗？

Prelude> length . show $ 10^1000000000
1000000001

当然,它确实需要相当多的记忆

但是如果你考虑一下 - 一个字节实际上可以存储高达256> 100的数字,即你可以在每个字节中存储两个以上的十进制数字.因此,具有十亿个数字的数字应该少于500 MB来存储......好吧,显然这里有一些开销需要乘法(当我show生成一个低效的列表字符串的数字时)但没什么戏剧性的.

顺便说一句,这不是Haskell/GHC进行这些计算,而是GHC使用的GMP.

但是你可以在Haskell中自己轻松实现这种类型.例如,为简单起见,您建议使用十进制数字列表^†

newtype DecDigit = DD { getDecDig :: Int }

instance Num [DecDigit] where
  fromInteger n | n < 10     = [DD $ fromInteger n]
                | otherwise  = let (cs,ls) = n`divMod`10
                               in DD $ fromInteger ls : fromInteger cs
  n + [] = n
  [] + n = n
  (DD n? : n) + (DD m? : m)
     | s?<10      = DD s? : n+m
     | otherwise  = DD (s?-10) : n+m+[DD 1]
   where s? = n?+m?

  ...

乘法有点困难,但基本上,如罗伯特哈维所说,这就像你用笔和纸计算的一样.

^† _{效率非常低!实际实现不使用十进制数字,而是充分利用机器大小的单词(可能使用现代处理器的128位甚至256位基本操作).}