Haskell递归列表理解导致C VoidCC VoidCC
因此，我正在制作一个素数列表，以帮助我使用简单的试除法来学习 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，这意味着取2个素数== [2, 3]，正确的？我不明白为什么这不起作用。希望更精通函数式编程黑魔法的人可以帮助我......
这是在拥抱，如果这有什么区别的话。
编辑-我能够想出这个解决方案（不太漂亮）：
primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) (takeWhile (<= (ceiling (sqrt (fromIntegral x)))) primes)]
编辑2-当通过 HUGS 或 GHCi 解释时，该程序工作正常，但是当我尝试用 GHC 编译它时，它输出 test: <<循环>>。有人知道问题是什么吗？
So I'm making a list of prime numbers to help me learn haskell using simple trial division (no fancy stuff until I get better with the language). I'm trying to use the following code:
primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]
This is loaded without an error. However:
>take 2 primes
[2ERROR - C stack overflow
I tried the same thing with nested list comprehensions. It doesn't work. I would guess that I'm making too many recursive calls, but this shouldn't be the case if i'm only computing one prime. In my mind the lazy evaluation should make it so that take 2 primes does something along the lines of:
primes = 2 : [ 3 | all (\p -> (mod 3 p) /= 0) [2] ]
Which doesn't require all that much computation - mod 3 2 == True, so all (\p -> (mod 3 p) /= 0) == True, which means take 2 primes == [2, 3], right? I don't understand why this isn't working. Hopefully someone much more versed in the black magic of functional programming can help me...
This is on HUGS, if that makes any difference.
EDIT- I was able to come up with this solution (not pretty):
primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) (takeWhile (<= (ceiling (sqrt (fromIntegral x)))) primes)]
EDIT2- The program works fine when interpreted through HUGS or GHCi, but when I try to compile it with GHC, it outputs test: <<loop>>. Anybody know what the problem is?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Hugs 不应该这样做，但无论如何代码都被破坏了，所以没关系。考虑一下：
如何确定 3 是否是质数？那么，mod 3 2 == 0 是吗？不。
mod 3 吗？？？ == 0 ？哎呀！两个素数之后的下一个元素是什么？我们不知道，我们正在尝试计算它。您需要添加一个排序约束，一旦所有小于sqrt x的 pelem素数都经过测试，该约束就会加 3（或任何其他x）。Hugs shouldn't do this, but the code is broken anyway so it doesn't matter. Consider:
How do you determine if 3 is prime? well, does
mod 3 2 == 0? No. Doesmod 3 ??? == 0? OOPS! What is the next element of primes after two? we don't know, we are trying to compute it. You need to add an ordering constraint that adds 3 (or any otherx) once all pelemprimes less thansqrt xhave been tested.所有人的文档都说“为了使结果为真，列表必须是有限的”
http://hackage.haskell.org /packages/archive/base/latest/doc/html/Prelude.html#v:all
The documentation for all says "For the result to be True, the list must be finite"
http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:all
前面的答案解释了为什么最初的理解不起作用，但没有解释如何编写一个可行的理解。
这是一个列表推导式，它递归地、惰性地（尽管效率不高）计算所有素数：
显然，我们不需要检查所有素数的 mod xp，我们只需要对小于潜在素数的 sqrt 的素数执行此操作。这就是 takeWhile 的用途。原谅
(\b -> (b * b) < x)这应该等价于(< sqrt x)但 Haskell 类型系统没有像那样。在我们将任何元素添加到列表之前，
x == 2会阻止 takeWhile 执行。The previous answers explained why the original comprehension didn't work, but not how to write one that would work.
Here is a list comprehension that recursively, lazily (albeit not efficiently) computes all primes:
Obviously we don't need to check mod x p for all primes, we only need to do it for primes less than the sqrt of the potential prime. That's what the takeWhile is for. Forgive the
(\b -> (b * b) < x)this should be equivalent to(< sqrt x)but the Haskell type system didn't like that.The
x == 2prevents the takeWhile from executing at all before we've added any elements to the list.