Haskell素数测试

Question

Haskell素数测试

8

我是Haskell的新手，正在学习：

isPrime :: Integer->Bool
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0])

我有几个问题。

为什么当我尝试加载 .hs 文件时，WinHugs 会显示：需要 (Floating Integer, RealFrac Integer) 的实例才能定义 isPrime？
当解释器在右侧集合中找到一个元素时，它会立即停止还是计算所有集合？我想你知道我的意思。

真抱歉我的英文不好。

- hsknew

5个回答

7

因为sqrt的类型是Floating a => a -> a。这意味着输入必须是Floating类型，输出也将是相同的类型。换句话说，x需要是Floating类型。但是你声明x的类型为Integer，而不是Floating类型。此外，floor需要一个RealFrac类型，所以x也需要是那种类型。

错误信息建议您通过定义实例Floating Integer（以及RealFrac）将Integer变成Floating类型来修复它。

当然，在这种情况下，这并不是正确的方法。相反，您应该使用fromIntegral将x转换为Real（它是Floating和RealFrac的实例），然后将其传递给sqrt。
是的。一旦==发现右操作数至少有一个元素，它就知道它不等于[]，因此返回False。

话虽如此，null是检查列表是否为空的更常用方式，而不是[] ==。

- sepp2k

2

对于惯用解决方案，我建议在第一项中使用 truncate . sqrt . fromIntegral，在第二项中使用 all (\y -> x \mod` y /= 0) [...]`。 - user395760

1

关于第二点，它会停止，例如：

[] == [x | x <- [1..]]

返回 False

- aromero

3

[x | x <- [1..]] 和 [1..] 是一样的。顺便提一下，它们都表示一个从 1 开始的无限列表。 - sepp2k

1

Landei的解决方案很棒，但是如果你想要一个更高效¹的实现，我们有（感谢BMeph）：

-- list of all primes
primes :: [Integer]
primes = sieve (2 : 3 : possible [1..]) where
     sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
     possible (x:xs) = 6*x-1 : 6*x+1 : possible xs

isPrime :: Integer -> Bool
isPrime n = shortCircuit || (not $ any divisible $ takeWhile inRangeOf primes) where
    shortCircuit = elem n [2,3] || (n < 25 && ((n-1) `mod` 6 == 0 || (n+1) `mod` 6 == 0))
    divisible y = n `mod` y == 0
    inRangeOf y = y * y <= n

“效率”来自于使用常数质数。它通过两种方式提高搜索效率：

Haskell运行时可以缓存结果，因此后续调用不需要重新计算
通过逻辑排除一定范围内的数字请注意，sieve值只是一个递归表格，其中列表头为质数，并将其添加到列表中。对于其余的列表，如果列表中没有其他组成该数字的值，则它也是质数。 possible是所有可能质数的列表，因为所有可能的质数都是6*k-1或6*k+1形式，除了2和3。对于shortCircuit也应用相同的规则，以便快速退出计算。

D.F.附注：
¹ 这仍然是一种非常低效的找素数的方法。如果你需要大于数千的素数，请使用筛法而不是试除法。在hackage上有几个更加高效的实现。

- langerra.com

为了使isPrime函数正常工作，必须移除shortCircuit。例如，它会匹配25，但25并不是质数。编译时，我需要在(not $ any divisible $ takeWhile inRangeOf primes)周围加上括号。 - rdrey

生成“质数”的代码在产生的质数数量上是“二次”的。埃拉托斯特尼筛法的理论时间复杂度是O(n*log n*log (log n))，其中n是产生的质数数量。试除法的理论复杂度为O(n^1.5/(log n)^0.5)。那么为什么这个看起来足够简单的试除法代码表现得如此糟糕呢？这是因为必须将每个过滤器的启动推迟到在输入流中看到该质数的平方时。将输入流稀释到三分之一只会减少常数因子，没有其他更多的改进。 - Will Ness

-2

我认为WinHugs需要导入一个整数等模块...尝试使用Int
解释器在你调用例如isPrime 32之前不会计算任何东西，然后它将惰性地计算表达式。

顺便说一下，你的isPrime实现并不是最好的实现！

- langerra.com

导入整数模块并不是问题；问题在于根据他的定义，“需要(Floating Integer, RealFrac Integer)的实例来定义isPrime”，就像WinHugs所说的那样。
是的，那又怎样？这太不相关了，我不知道该如何回应；首先，修复定义使其正常工作，然后再考虑如何使用它。PS）OP的isPrime实现并不是最好的，但这是“他”实现的！帮助解释如何修复他的实现，写出你自己的实现，或者离开！

- BMeph

你说得对，我已经很长时间没有使用Haskell了。
我试图让他知道Haskell的惰性也许太琐碎了。附注：他听起来像个学生，没有好的理由给他答案，他应该自己想出来。我有最优化的isPrime实现来自我的大学作业，但我不认为只是发布答案会有什么好处，因为他可能只是复制它并认为自己在Haskell上很厉害。
整理一下你的生活，有点尊严。

- langerra.com

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Landei · Accepted Answer

1) 问题在于 sqrt 的类型是 (Floating a) => a -> a，但您尝试使用整数作为参数。因此，您必须先将整数转换为浮点数，例如编写 sqrt (fromIntegral x)

2) 我看不出为什么 == 不应该是惰性的，但是要测试空集合，可以使用 null 函数（它绝对是惰性的，因为它适用于无限列表）：

isPrime :: Integer->Bool
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0]

为了获得更具通俗易懂的解决方案，我们需要将问题分解成较小的子问题。首先，我们需要一个包含所有满足 y*y <= x 的元素y的列表：

takeWhile (\y ->  y*y <= x) [2..]

我们只需要能够整除x的元素：

filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..])

然后我们需要检查该列表是否为空：

isPrime x = null (filter (\y ->  x `mod`y == 0) (takeWhile (\y ->  y*y <= x) [2..]))

如果这看起来对你来说太像Lisp了，可以用 $ 符号替换一些括号

isPrime x = null $ filter (\y ->  x `mod` y == 0) $ takeWhile (\y ->  y*y <= x) [2..]

为了更加清晰，您可以“外包”这些Lambda函数:

isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x

你可以将 null $ filter 替换为 not $ any，使其几乎“可读性好于人类”。

isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x