Haskell - 垃圾回收未能回收足够的空间

Question

我正在编写一个程序，用于计算从1到n之间所有奇数的总和：

oddSum' n result | n==0 = result
                 | otherwise = oddSum' (n-1) ((mod n 2)*(n)+result)

oddSum n = oddSum' n 0

我的输入得到了两个错误（下面是它们），我正在使用尾递归，那么为什么会发生堆栈溢出？（注意：我在Ubuntu上使用Hugs）

oddSum 20000 ERROR - 控制堆栈溢出

oddSum 100000 ERROR - 垃圾回收无法回收足够的空间

- user1493813

---

尝试使用ghc -O编译它，其严格性分析器可能会检测到oddSum'在第二个参数上是严格的，并自动插入所需的seq。 - Joachim Breitner

Answer 1

 oddSum 3
 oddSum 2 ((2 mod 2)*2 + 3)
 oddSum 1 ((1 mod 2)*1 + ((2 mod 2)*2 + 3))

你正在构建一个在result变量中的巨大thunk。 一旦你评估它，所有计算就必须同时完成，那么堆栈就会溢出，因为要执行加法，例如，你首先必须评估操作数和操作数的相加。

另一方面，如果thunk变得太大，就会导致堆溢出。

试着使用

result `seq` ((mod n 2) * n + result)

在递归中。

- Ingo

---

谢谢！我认为在 mod n 2 中加括号，变成 (mod n 2) 就可以强制它进行求值。 - user1493813

不会，除非编译器能够看到该值在函数中实际需要。例如，如果您将otherwise替换为result >= 0，则这将强制生成的代码在每次递归中评估result。（但我不建议这样做，这是一种损害可读性的技巧，也无法应用于所有情况。） - Ingo

Answer 2

首先，不要使用Hugs，它不受支持。通过优化GHC，类似这样的代码将被编译为紧凑高效的循环（但你的代码仍将存在问题）。

非严格的累加器总是存在积累巨大thunk的风险。解决方案之一是使其严格：

{-# LANGUAGE BangPatterns   #-}

oddSum' n !acc | n==0       = acc
               | otherwise  = oddSum' (n-1) $ (n`mod`2)*n + acc

当然，这并不是常规的写法；在Haskell中明确编写尾递归函数很繁琐且有些不受欢迎。大多数这类问题可以使用库函数轻松解决，例如：

oddSum n = sum [1, 3 .. n]

很不幸，这种方法即使在常规空间内也不能可靠地工作。它可以与折叠的严格版本配合使用（其中sum只是一种特化形式）。

import Data.List
oddSum n = foldl' (+) 0 [1, 3 .. n]

- leftaroundabout

---

我曾考虑使用列表来实现，但为了学习并不过于依赖已实现的函数，我选择了自己的实现方法。 我在我的大学计算机实验室，只有Hugs环境，学生无法安装任何软件（我在家使用ghc）。 - user1493813

Hugs不受支持，但Hugs 可用。它没有漏洞，编译速度很快（它甚至会注意到我编辑了文件，所以我不需要:r）。它仅限于Haskell 98，并且不支持GHC扩展，但它非常适合学习，部分原因是错误消息更清晰，特别是在ghc告诉你去编写实例声明的地方，它会给出类型错误。 - AndrewC

使用内存有限的Hugs引擎进行编程，揭示了提问者对于在Haskell中的求值有一个重要的误解，而这个误解可能被ghc -O2所隐藏。我们希望尽快发现自己的错误，不是吗？在编写代码时使用ghc -O2会比在ghci或hugs中的:r命令慢，并且不够交互，这是一种过早的优化。 - AndrewC

顺便说一句，我认为使用$!比Bang模式更好。oddSum' n acc | n == 0 = acc，然后 | otherwise = oddSum' (n-1) $! (mod n 2)*n + acc。 - AndrewC