Haskell 长度列表 + 阶乘

Question

我是 Haskell 的新手。我一直在尝试实现 n_choose_r，但由于某种原因，我的阶乘函数返回了奇怪的值。

Main.hs

factorial 0 = 1
factorial n = n * factorial (n-1)

subsets k list = factorial n where
    n = length list

一些不同的案例

> subsets 3 [1..4]
24 // correct value
> factorial 60
8320987112741390144276341183223364380754172606361245952449277696409600000000000000
> subsets 3 [1..60]
-8718968878589280256 // wrong value
> subsets 3 [1..100]
0 // wrong value

似乎列表越长，数字就越不稳定。谁能解释一下？

Answer 1

您的 factorial 函数是多态的：它的类型为 (Eq p, Num p) => p -> p。当你像 factorial 60 这样调用它时，p 被实例化为 Integer（这个选择称为 "type defaulting"），它是任意精度的并且没有上限。但是，length 在其输出中不是多态的：它总是 returns 一个 Int。 Haskell 不会自动为您在数字类型之间进行转换，因此当您使用 length 的结果调用 factorial 时，它也会使用 Int，它确实有上限，在您的情况下似乎是 9223372036854775807（您可以通过执行 maxBound :: Int 来验证）。要解决此问题，您可以自己将 Int 转换为 Integer：

subsets k list = factorial (toInteger n) where
    n = length list

或使用 genericLength，它与 length 相同，只是它的输出类型是多态的：

import Data.List

subsets k list = factorial n where
    n = genericLength list

请注意，如果您使用后一个选项，您需要注意不要做任何其他会强制使用 Int 而不是默认为 Integer.

的事情

Haskell 长度列表 + 阶乘

Haskell length list + factorial

haskell

integer-overflow