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 ERROR - 控制堆栈溢出

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

Answer 1

 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)

在递归中.

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]