scala - Scala 和 Haskell 中的阶乘

Question

Learn You a Haskell显示 factorial 函数:

Prelude> factorial n = product [1..n]

Prelude> factorial 50
30414093201713378043612608166064768844377641568960512000000000000

看起来 Int 大于 32 位，或者 Haskell 有类似 BigNumber 的类型。

在 Scala 中运行那个“类似”的函数。

scala> def factorial(n: Int) = List.range(1, n+1).foldLeft(1)(_*_)
factorial: (n: Int)Int

我可以计算一个保持在 Int.MaxValue(20 亿左右)范围内的阶乘

scala> factorial(10)
res5: Int = 362880

结果超过Int.MaxValue发生溢出

scala> factorial(33)
res6: Int = -2147483648

但是，为什么这里没有溢出呢？

scala> factorial(50)
res7: Int = 0

那么，它在 Haskell 中是如何工作的？而且，为什么 Scala 的结果为 0？

Answer 1

根据documentation :

The standard instances of Integral are Integer (unbounded or mathematical integers, also known as "bignums") and Int (bounded, machine integers, with a range equivalent to at least 29-bit signed binary)

Wikibooks 解释了这一点:

"Integer" is an arbitrary precision type: it will hold any number no matter how big, up to the limit of your machine's memory…. This means you never have arithmetic overflows. On the other hand it also means your arithmetic is relatively slow. Lisp users may recognise the "bignum" type here.

在 ghci 中:

Prelude> factorial 50 :: Int
-3258495067890909184
Prelude> factorial 50 :: Integer
30414093201713378043612608166064768844377641568960512000000000000

因此，对于 Int，它实际上会溢出。 Integer 可以容纳任何数字而不会因系统内存限制而溢出。