如何解决“堆栈空间溢出”在haskell [英] how to solve "stack space overflow" in haskell

问题描述

运行以下程序将打印出空间溢出：当前大小8388608字节。我已阅读此和这个，但仍不知道如何解决我的问题。我使用的是foldr，不应该保证它是尾递归的吗？

直到我知道我应该防止空间溢出当使用强大的递归。 ：）

 模块Main其中
导入Data.List 
 
值ab = $ b （b，b）$ b $（$ b $）$ l $ $ $ $ $ $ $ $ $ 
 $ b euler27 = let tuple_list = [value ab | （n，a，b）（max，v） - >如果n < -  [ -  999..999]，b < -  [ -  999..999]] 
 > max then（n，a * b）else（max，v））（0,0）tuple_list 
 main = print euler27 
  

编辑：为简单起见，删除 isPrime 的定义

解决方案

正如pierr回答，你应该使用 foldl'。更多细节：

• foldl'在给出之前计算它的左侧它到您的折叠步骤。


• foldr 为折叠步骤提供右侧值的thunk。这个thunk将在需要时计算。

让我们和 foldr

  foldr（+）0 [1..3] 
 1 + foldr （+）0 [2..3] 
 1 + 2 + foldr（+）0 [3] 
 1 + 2 + 3 + foldl（+）0 []  - .. 
 1 + 2 + 3 + 0 
 1 + 2 + 3 
 1 + 5 
 6 
  

以及 foldl' :(代码中省略了标签，因为SO不会很好地显示它）

  foldl（+）0 [1..3] 
  -  seq是一个严格提示。 
  - 这意味着x在foldl 
x`seq` foldl（+）x [2..3]之前计算，其中x = 0 + 1 
 foldl（+）1 [ 2 + 3 
x`seq` foldl（+）x [3]其中x = 1 + 2 
 foldl（+）3 [3] 
x`seq` foldl（+）x []其中x = 3 + 3 
 foldl（+）6 [] 
 6 
  

适用于 foldr ，不会泄漏。 步必须：



• 返回一个不依赖于右侧的结果，忽略它或包含它在一个懒惰的结构中


• 返回右侧

好的 foldr 用法：

   - 在map中，该步骤返回结构头
  - 不评估右侧
 map f = foldr（（（）。f）[] 
 
过滤器f = 
 foldr step [] 
其中
 step x rest = 
 | f x = x：rest  - 返回结构头部
 |否则=休息 - 返回右侧原样是
 
任何f = 
 foldr步骤False 
其中
  - 可以使用step x rest = fx ||休息。这是相同的。 
  - 以下版本用于详细说明
 step x rest 
 | f x =真 - 忽略右边
 |否则=休息 - 按照
  

返回右侧

Running the following program will print "space overflow: current size 8388608 bytes." I have read this and this, but still don't know how to resolve my problem. I am using foldr, shouldn't it be guaranteed to be "tail recursive"?

I feel great about Haskell so far until I know I should prevent "space overflow" when using the powerful recursion. :)

module Main where
import Data.List

value a  b = 
  let l = length $ takeWhile (isPrime) $ map (\n->n^2 + a * n + b) [0..]
  in (l, a ,b)

euler27 = let tuple_list = [value a b | a <-[-999..999] , b <- [-999..999]]
      in foldr (\(n,a,b) (max,v) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list
main = print euler27

EDIT: remove the definiton of isPrime for simplicity

解决方案

As pierr answered, you should use foldl'. For more details:

• foldl' calculates its "left-side" before giving it to your fold step.
• foldr gives your fold step a "thunk" for the right-side value. This "thunk" will be calculated when needed.

Let's make a sum with foldr and see how it evaluates:

foldr (+) 0 [1..3]
1 + foldr (+) 0 [2..3]
1 + 2 + foldr (+) 0 [3]
1 + 2 + 3 + foldl (+) 0 [] -- this is a big thunk..
1 + 2 + 3 + 0
1 + 2 + 3
1 + 5
6

And with foldl': (tag omitted in code because SO doesn't display it nicely)

foldl (+) 0 [1..3]
-- seq is a "strictness hint".
-- here it means that x is calculated before the foldl
x `seq` foldl (+) x [2..3] where x = 0+1
foldl (+) 1 [2..3]
x `seq` foldl (+) x [3] where x = 1+2
foldl (+) 3 [3]
x `seq` foldl (+) x [] where x = 3+3
foldl (+) 6 []
6

In good uses for foldr, which don't leak. the "step" must either:

• Return a result that doesn't depend on the "right-side", ignoring it or containing it in a lazy structure
• Return the right-side as is

Examples of good foldr usage:

-- in map, the step returns the structure head
-- without evaluating the "right-side"
map f = foldr ((:) . f) []

filter f =
  foldr step []
  where
    step x rest =
      | f x = x : rest -- returns structure head
      | otherwise = rest -- returns right-side as is

any f =
  foldr step False
  where
    -- can use "step x rest = f x || rest". it is the same.
    -- version below used for verbosity
    step x rest
      | f x = True -- ignore right-side
      | otherwise = rest -- returns right-side as is

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