haskell - Haskell - 垃圾收集无法回收足够的空间

Question

我正在做一个程序来总结所有奇数到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 错误 - 控制堆栈溢出

oddSum 100000 错误 - 垃圾收集无法回收足够的空间

score 8 · Accepted Answer

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

您正在result变量中构建一个巨大的 thunk。一旦你计算了这个，所有的计算都必须一次完成，然后堆栈溢出，因为，例如，要执行加法，你首先必须计算操作数，以及操作数中加法的操作数。

如果，otoh，thunk 变得太大，你会得到一个堆溢出。

尝试使用

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

在递归中。

score 8 · Accepted Answer

首先，不要使用 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]

2 回答 2