如何避免堆栈空间溢出？ [英] How to avoid stack space overflows?

问题描述

如果我需要获取包含内存密集型元素的大型列表的值，那么我会对GHC投掷堆栈溢出感到有些惊讶。
我确实预计GHC有TCO，所以我永远不会遇到这种情况。

为了最简单的情况，请看以下直接实现的返回斐波纳契数的函数（取自HaskellWiki）。

  import Data.List 
 
＃雅致的递归定义
 $ fib $ = 0：1：zipWith（+）fibs（tail fibs）
 
＃使用Data.List中的unfoldr有点棘手
 fibs'= unfoldr（\（a，b ） - > Just（a，（b，a + b）））（0,1）
 
＃使用迭代的版本
 fibs''= map fst $ iterate（\（ a，b） - >（b，a + b））（0,1）
 
＃按定义计算数量
 fib_at 0 = 0 
 fib_at 1 = 1 
 fib_at n = fib_at（n-1）+ fib_at（n-2）
 
 main = do 
 { - 所有以下表达式中止
堆栈空间溢出：当前大小8388608字节。 
使用'+ RTS -Ksize -RTS'来增加它。 
  - } 
 print $ fibs !! （10 ^ 6）
打印。最后$ take（10 ^ 6）fibs 
 print $ fibs'!! （10 ^ 6）
 print $ fibs''!! （10 ^ 6）
 
  - 以下表达式在几个
  - 分钟之后没有完成
 print $ fib_at（10 ^ 6）
  

源代码编译为 ghc -O2 。

我做错了什么？我希望避免使用增加的堆栈大小或其他特定的编译器选项来重新编译。 解决方案

这些 链接 这里会给你一个很好的介绍你的问题（太空漏洞）。

如果你知道要注意什么（并且有一个漂亮的懒惰评估模型），例如：

  { - ＃LANGUAGE BangPatterns＃ - } 
 
 import Data.List 
 
 fibs'= unfoldr（\（！a，！b） - > Just（a，（b，a + b）））（0,1）
 
 main = do 
 print $ fibs'!! （10 ^ 6） - 不再有堆栈溢出
  

I've been a bit surprised by GHC throwing stack overflows if I'd need to get value of large list containing memory intensive elements. I did expected GHC has TCO so I'll never meet such situations.

To most simplify the case look at the following straightforward implementations of functions returning Fibonacci numbers (taken from HaskellWiki). The goal is to display millionth number.

import Data.List

# elegant recursive definition
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

# a bit tricky using unfoldr from Data.List
fibs' = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

# version using iterate
fibs'' = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

# calculate number by definition
fib_at 0 = 0
fib_at 1 = 1
fib_at n = fib_at (n-1) + fib_at (n-2)

main = do
    {-- All following expressions abort with
        Stack space overflow: current size 8388608 bytes.
        Use `+RTS -Ksize -RTS' to increase it.
     --}
    print $ fibs !! (10^6)
    print . last $ take (10^6) fibs
    print $ fibs' !! (10^6)
    print $ fibs'' !! (10^6)

    -- following expression does not finish after several 
    -- minutes
    print $ fib_at (10^6)

The source is compiled with ghc -O2.

What am I doing wrong ? I'd like to avoid recompiling with increased stack size or other specific compiler options.

解决方案

These links here will give you a good introduction to your problem of too many thunks (space leaks).

If you know what to look out for (and have a decent model of lazy evaluation), then solving them is quite easy, for example:

{-# LANGUAGE BangPatterns #-}                        

import Data.List                                     

fibs' = unfoldr (\(!a,!b) -> Just (a,(b,a+b))) (0,1) 

main = do                                            
    print $ fibs' !! (10^6)  -- no more stack overflow                   

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