Haskell foldl和堆栈溢出？ [英] Haskell foldl and stack overflow?

问题描述

我读了一篇文章，声称 foldl 很容易发生堆栈溢出。发布示例代码为：

 最大值[1..1000000] 
  

代码不会在我的机器中溢出。然而，它可能因环境而异。我增加了这样的数字：

 最大值[1..1000000000] 
  

导致硬盘交换，所以我不得不停止评估。
示例代码并不重要。它真的发生堆栈溢出吗？或仅仅是一个过去的故事？

解决方案

一些要点

• 递归函数在每个调用中占用堆栈空间，所以深度嵌套的调用会导致溢出


• 尾递归函数可以优化迭代，因此不会溢出
li>

• foldr 是不是尾递归


• 懒惰评估可以防止tail-recursive functions from being optimized


• foldl 是尾递归和懒惰的，所以它可以溢出


• foldl'是尾递归和严格的，因此它是安全的

I read a posting claims foldl may occur stack overflow easily. And the posting sample code was:

maximum [1..1000000]

The code doesn't overflown in my machine. However it can vary by environment. I increased number like this:

maximum [1..1000000000]

it caused hard disk swapping, so I have to stop evaluation. Sample code is not important. Is it really occur stack overflow? Or just an old days story?

解决方案

Some points

• Recursive function take stack space in each call, so deeply nested calls will cause overflows
• Tail-recursive function can be optimized to iterations and therefore don't overflow
• foldr is not tail-recursive
• Lazy evaluation can prevent tail-recursive functions from being optimized
• foldl is tail-recursive and lazy, so it can overflow
• foldl' is tail-recursive and strict, so it's safe

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