Project Euler 27 上的 C 堆栈溢出
我刚刚开始学习 Haskell，并将阅读书籍和教程与解决 Project Euler 的问题结合起来。 我一直停留在 问题 27 上，因为我收到“C 堆栈溢出”使用此代码时出错：
euler.hs
divisors n = [x | x <- [1..n `div` 2], n `mod` x == 0] ++ [n]
is_prime n = divisors n == [1, n]
f a b = [n^2 + a * n + b | n <- [0..]]
primes_from_zero a b = length(takeWhile is_prime (f a b))
命令窗口
此命令给出欧拉系数 1 和 41（行中 40 个素数），
foldr (max) (0, 0, 0) [(primes_from_zero a b, a, b) | a <- [0..10], b <- [0..50]]
此命令因“C 堆栈溢出”而失败（我想要获取问题定义中也提到的系数-79和1601）：
foldr (max) (0, 0, 0) [(primes_from_zero a b, a, b) | a <- [-100..0], b <- [1500..1700]]
请告诉我为什么会出现错误以及如何解决它？ 谢谢你！
我用WinHugs。
I just have started to learn Haskell and combine reading books and tutorials with solving problems from Project Euler. I have stuck on Problem 27 because I get "C stack overflow" error using this code:
euler.hs
divisors n = [x | x <- [1..n `div` 2], n `mod` x == 0] ++ [n]
is_prime n = divisors n == [1, n]
f a b = [n^2 + a * n + b | n <- [0..]]
primes_from_zero a b = length(takeWhile is_prime (f a b))
command window
this command gives Euler's coefficients 1 and 41 (40 primes in row)
foldr (max) (0, 0, 0) [(primes_from_zero a b, a, b) | a <- [0..10], b <- [0..50]]
this one fails with "C stack overflow" (I wanted to obtain coefficients -79 and 1601 also mentioned in the problem definition):
foldr (max) (0, 0, 0) [(primes_from_zero a b, a, b) | a <- [-100..0], b <- [1500..1700]]
Would you tell me, please, why does the error arise and how to resolve it? Thank you!
I use WinHugs.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
“堆栈溢出”错误意味着程序中的函数调用链（从入口函数到当前正在执行的函数）变得太大。 大多数编译器和运行时将调用链实现为堆栈数据结构 - 每个元素都是一个“堆栈帧”，包含单个函数调用的局部变量和上下文 - 大小有限。
通常，堆栈溢出意味着递归函数出现问题。 例如，如果递归永远不会终止，它最终将达到堆栈限制并“溢出”。 即使递归正在终止，如果调用太多，它也可能会溢出。 对于非常大的列表，通常会出现这种情况，并且您的示例似乎也是这种情况。
在 Haskell（以及许多其他语言）中避免堆栈溢出的一种方法是编写 尾递归函数。 尾递归函数是唯一的递归调用是函数结果的函数。 例如，
相比之下，foldr 不是尾递归
出于技术原因，尾递归调用可以重用其调用者的堆栈帧，因此不会导致调用堆栈增长。
（附注：
foldr不是尾递归，但比foldl更“懒惰”，因为它可能不需要评估整个列表。这可能会指导您决定使用哪个）即使使用尾递归函数，您也可能会由于 " 而耗尽内存空间泄漏”。 例如，在
foldl中，每个递归调用都会为(fxy)构建一个新的暂停。foldl使用常量堆栈空间，但对f的未计算调用使用 O(n) 空间。 为了在需要严格性的情况下避免这种情况，您可以使用foldl'，其中中缀运算符
$!强制严格求值。A "stack overflow" error means that the chain of function calls in your program (from the entry function down to the currently executing function) has grown too large. Most compilers and runtimes implement the call chain as a stack data structure—each element is a "stack frame" containing the local variables and context of a single function call—with a limited size.
Usually, a stack overflow means there's something wrong with a recursive function. For example, if a recursion never terminates, it will eventually hit the stack limit and "overflow." Even if a recursion is terminating, it may overflow if there are simply too many calls. This is often the case with very large lists, and seems to be the case with your example.
One way to avoid stack overflows in Haskell (and many other languages) is to write tail-recursive functions. A tail-recursive function is one where the only recursive call is the result of the function. For example,
In contrast,
foldris not tail recursiveFor technical reasons, a tail recursive call can re-use the stack frame of its caller, and thus does not cause the call stack to grow.
(A side note:
foldris not tail recursive but is "lazier" thanfoldl, because it may not need to evaluate the whole list. This may guide your decision on which to use.)Even with a tail-recursive function, you may run out of memory due to a "space leak". For example, in
foldleach recursive call will build a new suspension for(f x y).foldluses constant stack space, but O(n) space for unevaluated calls tof. To avoid this in cases where strictness is desirable, you can usefoldl'where the infix operator
$!forces strict evaluation.我不知道为什么 litb 将他的答案放入评论而不是答案中，所以我将其复制到这里人们会看到它：
http://www.haskell.org/haskellwiki/Stack_overflow
我认为这是正确的答案。 但简短的版本是，foldr 不是尾递归。
我已将这篇文章标记为社区 Wiki，因此我不会从中获得任何声誉。
I don't know why litb put his answer into a comment instead of an answer, so I'm copying it here so that people will see it:
http://www.haskell.org/haskellwiki/Stack_overflow
I think it's the right answer. But the short version is that foldr is not tail recursive.
I've marked this post as Community Wiki, so I won't get any reputation from it.