4

我刚刚开始学习 Haskell，并将阅读书籍和教程与解决 Project Euler 的问题结合起来。我一直坚持问题 27，因为使用以下代码出现“C 堆栈溢出”错误：

欧拉文件

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。

4

2 回答 2

9

“堆栈溢出”错误意味着程序中的函数调用链（从入口函数到当前执行的函数）变得太大。大多数编译器和运行时都将调用链实现为堆栈数据结构——每个元素都是一个“堆栈框架”，包含单个函数调用的局部变量和上下文——大小有限。

通常，堆栈溢出意味着递归函数有问题。例如，如果递归永远不会终止，它最终会达到堆栈限制并“溢出”。即使递归终止，如果调用太多，它也可能溢出。非常大的列表通常是这种情况，您的示例似乎就是这种情况。

在 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

中缀运算符$!强制进行严格评估的地方。

于 2008-12-16T14:57:03.247 回答
3

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

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

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

我已将此帖子标记为社区 Wiki，因此我不会从中获得任何声誉。

于 2008-12-16T14:08:31.723 回答