haskell - haskell中的素数程序

Question

我正在 Haskell 中查找一个程序，该程序测试给定的数字是否为素数。

prime :: (Integral a) => a -> Bool
prime 1 = True
prime x = and [ x `mod` y /= 0 | y <- [2..(x-1)] ]

我不明白这个 and 的用途是什么:prime x = and [。

Answer 1

虽然这个问题已经得到解答，但请允许我补充一些内容:当检查和的来源时，你会得到:

and :: [Bool] -> Bool
and = foldr (&&) True

首先要注意的是 and 接受 bool 变量列表，并返回单个 bool 变量，并且表达式 x mod y/= 0 的计算结果为True 或 False(因此符合 [Bool] 要求)。

更重要的是要注意 foldr 是一个惰性折叠。因此，这里的惰性折叠是最佳的，因为 && 是一个半严格运算符。因此，惰性折叠与半严格运算符的结合将在第一次出现 False 时产生短路求值。因此，在实际的非质数的情况下，和将避免评估整个列表，从而节省您的时间。不要相信我的话，如果需要的话，定义您自己的严格版本的 and (使用更严格的 foldl):

andStrict :: [Bool] -> Bool
andStrict x = foldl (&&) True

primeStrict :: (Integral a) => a -> Bool
primeStrict x = andStrict [x `mod` y /= 0 | y <- [2..(x-1)]]

现在运行:

prime 2000000000

注意到速度有多快了吗？现在执行此操作，但在内存堆栈崩溃之前中断它:

primeStrict 2000000000

这显然慢了，你可以打断它。这就是 and 的作用，这就是为什么 and 是用 foldr 编写的，也是为什么您发布的示例代码选择它的原因。希望这有助于作为支持性答案。