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))

命令窗口

此命令给出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.

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

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

避免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

中缀操作员$!强制进行严格评估.