Haskell 空间溢出 [英] Haskell Space Overflow

问题描述

我已经编译了这个程序并正在尝试运行它.

I've compiled this program and am trying to run it.

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 得到以下信息

I'm getting the following from GHC

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

我认为这是我听说过的空间溢出"之一.(我对 Haskell 很陌生.)我该如何解决?我是否必须将 collat​​zLength 重写为尾递归?

I assume this is one of the "space overflow" things I've been hearing about. (I'm pretty new to Haskell.) How do I fix it? Do I have to rewrite collatzLength to be tail recursive?

推荐答案

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

As the author of the code in question, I am now slightly embarrassed because it has not one but two possible stack overflow bugs.

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

1. It uses Int. On a 32-bit system this will overflow, as the Collatz sequence can go quite a bit higher than the starting number. This overflow can cause infinite recursion as the function jumps back and forth between negative and positive values.

对于 1 到 100 万之间的数字，最坏的起点是 704511，最高可达 56,991,483,520，然后又回到 1.这远超出 32 位范围.

In the case of numbers between one and a million, the worst starting point is 704511, which goes as high as 56,991,483,520 before coming back down towards 1. This is well outside the 32-bit range.

它使用maximumBy.这个函数并不严格，所以在长列表上使用时会导致堆栈溢出.对于默认堆栈大小，一百万个元素已经足够了.不过，由于 GHC 执行的严格性分析，它仍然可以在启用优化的情况下工作.

It uses maximumBy. This function is not strict, so it will cause a stack overflow when used on long lists. One million elements is more than enough for this to happen with the default stack size. It still works with optimizations enabled, though, due to the strictness analysis performed by GHC.

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

The solution is to use a strict version. Since none is available in the standard libraries, we can use the strict left fold ourselves.

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

Here is an updated version which should (hopefully) be stack overflow-free, even without optimizations.

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

这篇关于Haskell 空间溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！