Haskell空间溢出

Question

我编译了这个程序,并试图运行它.

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Int -> Int
collatzLength = Memo.arrayRange (1, 1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ maximumBy (comparing fst) $ [(collatzLength n, n) | n <- [1..1000000]]

我从GHC获得以下内容

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

我认为这是我听说过的"空间溢出"之一.(我对Haskell很新.)我该如何修复它？我是否必须重写collat​​zLength才能进行尾递归？

Answer 1

作为相关代码的作者,我现在有点尴尬,因为它只有两个可能的堆栈溢出错误.

1. 它使用Int.在32位系统上,这将溢出,因为Collat​​z序列可能比起始编号高很多.当函数在负值和正值之间来回跳转时,这种溢出会导致无限递归.

   在数字介于1和100之间的情况下,最差的起点是704511,高达56,991,483,520,然后再回落到1.这远远超出了32位的范围.

2. 它使用maximumBy.此函数不严格,因此在长列表上使用时会导致堆栈溢出.使用默认堆栈大小,一百万个元素就足以实现这一点.但是,由于GHC执行了严格的分析,它仍然可以启用优化.

   解决方案是使用严格的版本.由于标准库中没有可用的,我们可以自己使用严格的左侧折叠.

这是一个更新版本,即使没有优化,也应该(希望)堆栈无溢出.

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Integer -> Integer
collatzLength = Memo.arrayRange (1,1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]]

Answer 2

这是一个更短的程序,以同样的方式失败:

main = print (maximum [0..1000000])

是的.

$ ghc --make harmless.hs && ./harmless
[1 of 1] Compiling Main             ( harmless.hs, harmless.o )
Linking harmless ...
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

随着-O2它工作.我该怎么做？我不知道:(这些太空神秘是一个严重的问题.

编辑:

对于哈马尔来说,指出罪魁祸首.

更改您要使用的程序

maximum' = foldl1' max

使它没有工作-O2.Prelude's 的实现maximum是懒惰的,因此对于没有编译器魔法灰尘的长列表来说也不太适用.

Answer 3

我认为你最有可能用一些Collat​​z序列击中整数溢出,然后最终进入一个包含溢出但从未命中1的"人工"循环.这将产生无限递归.

请记住,一些Collat​​z序列在它们最终(？)结束为1之前会比它们的起始数字大得多.

尝试看看它是否修复了您的问题,Integer而不是使用Int.