我正在 Haskell 中查找一个程序,该程序测试给定的数字是否为素数。
prime :: (Integral a) => a -> Bool
prime 1 = True
prime x = and [ x `mod` y /= 0 | y <- [2..(x-1)] ]
我不明白这个 and
的用途是什么:prime x = and [
。
最佳答案
虽然这个问题已经得到解答,但请允许我补充一些内容:
当检查和
的来源时,你会得到:
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
编写的,也是为什么您发布的示例代码选择它的原因。希望这有助于作为支持性答案。
关于haskell - haskell中的素数程序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23135182/