Haskell整数类型签名

Question

假设我想编写一个函数来判断给定的整数是否为素数，那么我应该使用哪种类型签名？

  isPrime :: Int -> Bool

或者

  isPrime :: (Integral a) => a -> Bool

两者有什么区别？选择它们的特定原因是什么？
如果有，分别在哪些情况下应该使用它们？

- manuzhang

Answer 1

类型 Int -> Bool 表示你的函数操作的是类型为 Int 的值，这些值是大小受限的整数（最大值取决于机器）。

类型 (Integral a) => a -> Bool 表示你的函数操作的是任何具有 Integral 类型类实例的类型的值——即在特定情况下“行为类似”于整数的类型。选择这种类型而不是具体类型的主要原因是创建更通用的函数。

使用 Integral 的通用形式在需要在其他上下文中使用类似整数的类型时最有用，一个很好的例子是标准库不能处理这样的地方，例如像 replicate :: Int -> a -> [a] 这样的函数。因此，在其自己的目的上操作某个特定类似整数的类型的代码想要将该类型与 replicate 一起使用，则需要首先转换为 Int，或从 Data.List 导入 genericReplicate。

在您的情况下，您可能需要考虑的是类型 Integer，表示任意大小的整数。由于您的主要目标是计算，支持任意整数类型的价值较小。

如果我没记错的话，标准库中 Integral 的唯一实例是 Int 和 Integer。（编辑：正如 hammar 在评论中提醒我的，Data.Int 和 Data.Word 中也有固定大小类型的实例。还有像 CInt 这样的外部类型，但我故意忽略了这些。）

- C. A. McCann

---

在 Data.Int 和 Data.Word 中也有固定大小的类型。 - hammar

@hammar：啊，对了！我忘记那些实际上是标准库的一部分了，谢谢。 - C. A. McCann

@DanielFischer’╝ܵłæµā│instance HasPrimes IntegerÕÆīisIntegralPrime :: Integral a => a -> Bool; isIntegralPrime = isPrime . toIntegerÕ░▒ĶČ│Õż¤õ║å’╝īĶĆīõĖŹµś»õĖĆõĖ¬ķ╗śĶ«żÕ«×õŠŗŃĆé - rampion

@rampion 是的，我认为那样做很好。 - Daniel Fischer

@DanielFischer: 或者，如果你想将 HasPrimes 限制为 Integral 类型，你可以在类本身中使用默认实现：class Integral a => HasPrimes a where isPrime :: a -> Bool ; isPrime = isIntegerPrime . toInteger。 - rampion

Answer 2

我建议使用签名。

isPrime :: Integer -> Bool

一个签名isPrime :: Int -> Bool会排除对于较大的数字进行快速测试，因为这些测试通常会溢出（从技术上讲，至少在由integer-gmp提供的版本中，这也适用于Integer，但是在这些问题变得重要之前，您很可能已经没有足够的内存了，因此我们可以维护无限的Integer类型的虚构）。

一个类型isPrime :: Integral a => a -> Bool将是任何可行实现的谎言。可以为模拟Z[sqrt(2)]的类型建立Integral实例（尽管对于这样的类型，toInteger是不忠实的），对于这样的类型，2不是质数，如何使用通用测试检测？

或者考虑模拟因子环Z/(n)的有限类型。这种类型的Ord实例与算术不兼容，但我们已经为Int等类型做到了这一点。例如，在Z(6)={0,1,2,3,4,5}中，质数是2、3和4（请注意，它们中没有一个是不可约元素，2 = 4*2，3 = 3*3，4 = 2*2）。

因此，唯一有意义且可行的测试是，“它是一个有理（或自然）质数，其值恰好在类型范围内吗？”这在类型isPrime :: Integer -> Bool中得到了捕捉（尽可能不牺牲太多速度），在适当时与toInteger组合。

- Daniel Fischer

---

这不是我的问题，但为什么5不是质数，因为5是非零非单位的，而且 5 | 1*5 => 5 | 5；另外为什么2和3不是不可约的。 - manuzhang

5是一个单位，5*5 = 1。我们可以写成2 = 4*2，其中4和2都不是单位，以及3 = 3*3，其中3和3也都不是单位，因此2和3是可约的。另一方面，如果2整除a*b，那么2必须已经整除了a或b（这是从Z继承来的），所以2是质数（或者说，(Z/6)/2 ~ Z/3，即由2生成的理想在Z/(6)上的商环是域Z/(3)，特别地是一个整环）。3同理。 - Daniel Fischer

我想我最好翻看一本抽象代数的书，而不是在这里打扰您关于基础概念；那么你觉得我们不能用Haskell或其他编程语言处理这样的东西吗？ - manuzhang

哦，那些概念并不是那么基础。但如果你想学习的话，一本好书肯定比 SO 评论中有限的空间更好的方法。处理这样的东西并不是简单的，Integral 类也不是正确的方法，但 rampion 在 C.A. McCann 的回答的评论中提出了一个 HasPrimes 类，然后每个实例将负责在该情况下正确的行为。请注意，像 Z/(6) 这样的具有零除数环中的素数并不是非常有趣的。但其他例子或多项式环是有趣的，并且不适合 Integral 紧身衣。 - Daniel Fischer

Answer 3

许多素性测试都是概率性的，需要随机数，因此至少在最低层次上，它们的类型签名将像这样：

seemsPrime :: (Integral a) => a -> [a] -> Bool

积分约束似乎是合理的，因为通常您不需要具体类型，而只需要像 rem 这样的操作。

- ertes

---

嗯，概率测试需要单子返回类型：seemsPrime :: (Integral a) => a -> [a] -> IO Bool。 - wvoq