haskell - Project Euler 27 上的 C 堆栈溢出

Question

我刚刚开始学习 Haskell，并将阅读书籍和教程与解决 Project Euler 的问题结合起来。我一直坚持Problem 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。

Answer 1

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

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

避免 Haskell(以及许多其他语言)中堆栈溢出的一种方法是编写 tail-recursive functions 。尾递归函数是唯一的递归调用是函数结果的函数。例如，

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 更“懒惰”，因为它可能不需要评估整个列表。这可能会指导您决定使用哪个。)

即使使用尾递归函数，您也可能会由于"space leak"而耗尽内存。 。例如，在foldl中，每个递归调用将为(f x y)构建一个新的暂停。 foldl 使用常量堆栈空间，但 O(n) 空间用于对 f 的未评估调用。为了在需要严格性的情况下避免这种情况，您可以使用 foldl'

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

其中中缀运算符$!强制严格求值。