c堆栈溢出项目Euler 27

Question

我刚刚开始学习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))

命令窗口

该命令给出了Euler的系数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。

Answer 1

“堆栈溢出”错误意味着您程序中的函数链条调用（从输入函数到当前执行函数）变得太大了。大多数编译器和运行时间将呼叫链作为堆栈数据结构实现 - 每个元素是包含局部变量和单个函数调用的上下文的“堆栈帧”，其大小有限。

通常，堆栈溢出意味着递归功能有问题。例如，如果递归永不终止，它将最终达到堆栈限制和“溢出”。即使递归正在终止，如果呼叫太多，它也可能溢出。通常，列表非常大，您的示例似乎就是这种情况。

避免在Haskell（以及许多其他语言）中堆叠溢出的一种方法是写 尾部回复功能. 。尾部回复功能是唯一的递归调用是该函数的结果。例如，

foldl f x (y:ys) = foldl f (f x y) ys

相比之下， foldr 不是尾部递归

foldr f x (y:ys) = f y (foldr f x ys)

出于技术原因，尾递归电话可以重新使用呼叫者的堆栈框架，因此不会导致调用堆栈增长。

（旁注： foldr 不是尾部递归，而是“懒惰” foldl, ，因为它可能不需要评估整个列表。这可能指导您使用哪些决定。）

即使具有尾部回复功能，您也可能由于 “空间泄漏”. 。例如，在 foldl 每个递归电话都会为 (f x y). foldl 使用恒定的堆栈空间，但o（n）空间用于未评估的呼叫 f. 。为了避免这种严格性，您可以使用 foldl'

foldl' f x (y:ys) = (foldl' f $! f x y) ys

infix操作员的位置 $! 强迫评估。

Answer 2

我不知道为什么 litb 将他的答案评为评论而不是答案，因此我在这里复制它，以便人们看到它：

http://www.haskell.org/haskellwiki/stack_overflow

我认为这是正确的答案。但是简短的版本是foldr不是尾部递归。

我将这篇文章标记为社区Wiki，因此我不会从中获得任何声誉。