2

所以我正在制作一个素数列表来帮助我使用简单的试除法学习haskell（在我对语言变得更好之前没有花哨的东西）。我正在尝试使用以下代码：

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]

这是加载没有错误。然而：

>take 2 primes
[2ERROR - C stack overflow

我用嵌套列表推导尝试了同样的事情。它不起作用。我猜我做了太多递归调用，但如果我只计算一个素数，情况就不应该如此。在我看来，懒惰的评估应该可以做到take 2 primes以下几点：

primes = 2 : [ 3 | all (\p -> (mod 3 p) /= 0) [2] ]

哪个不需要那么多计算 - mod 3 2 == True，所以all (\p -> (mod 3 p) /= 0) == True，这意味着take 2 primes == [2, 3]，对吗？我不明白为什么这不起作用。希望更精通函数式编程黑魔法的人可以帮助我......

这是在拥抱，如果这有什么不同的话。

编辑-我能够想出这个解决方案（不漂亮）：

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) (takeWhile (<= (ceiling (sqrt (fromIntegral x)))) primes)]

EDIT2- 当通过 HUGS 或 GHCi 解释时，该程序工作正常，但是当我尝试用 GHC 编译它时，它输出test: <<loop>>. 有人知道问题是什么吗？

4

3 回答 3

7

拥抱不应该这样做，但无论如何代码都被破坏了，所以没关系。考虑：

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]

如何判断 3 是否为素数？嗯，是mod 3 2 == 0吗？不，有mod 3 ??? == 0吗？哎呀！两个后素数的下一个元素是什么？我们不知道，我们正在尝试计算它。您需要添加一个排序约束，一旦所有小于xp的素数都经过测试，就会添加 3 （或任何其他 ）。elemsqrt x

于 2011-03-04T21:31:12.293 回答
3

所有人的文档都说“要使结果为真，列表必须是有限的” http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:all

于 2011-03-04T22:08:06.720 回答
0

先前的答案解释了为什么原始理解不起作用，但没有解释如何编写一个可以起作用的。

这是一个递归地、惰性地（尽管效率不高）计算所有素数的列表推导：

let primes = [x | x <- 2:[3,5..], x == 2 || not (contains (\p -> 0 == (mod x p)) (takeWhile (\b -> (b * b) < x) primes))]

显然我们不需要检查所有素数的 mod xp，我们只需要检查小于潜在素数 sqrt 的素数。这就是 takeWhile 的用途。请原谅(\b -> (b * b) < x)this 应该等同于(< sqrt x)但 Haskell 类型系统不喜欢那样。

x == 2在我们将任何元素添加到列表之前，这完全阻止了 takeWhile 的执行。

于 2011-07-11T02:14:47.617 回答