Geek Answers Handbook

How to solve "stack overflow" in haskell

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

I still have a great relationship with Haskell, until I know that I should prevent "space overflow" when using powerful recursion. :)

module Main where import Data.List value ab = let l = length $ takeWhile (isPrime) $ map (\n->n^2 + a * n + b) [0..] in (l, a ,b) euler27 = let tuple_list = [value ab | 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 isPrime definition for simplicity

+4
source share
2 answers

As pierr replied, you should use foldl' . For more information:

  • foldl' calculates its “left side” before passing it to the fold step.
  • foldr gives your focus the thunk step for the right value. This "thunk" will be calculated when necessary.

Make a sum with foldr and see how it is valued:

 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' : (the tag is missing in the code because SO does not display it beautifully)

 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 use for foldr that do not leak. The "step" should either:

  • Returns a result that is independent of the "right side", ignores it, or contains it in a lazy structure
  • Bring back the right side, like

Examples of good use of foldr :

 -- 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 = | fx = x : rest -- returns structure head | otherwise = rest -- returns right-side as is any f = foldr step False where -- can use "step x rest = fx || rest". it is the same. -- version below used for verbosity step x rest | fx = True -- ignore right-side | otherwise = rest -- returns right-side as is
+11
source

replace

 foldr (\(n,a,b) (max,v) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list

with

 foldl' (\(max ,v) (n,a,b) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list

solved this problem if we suggested that we always prefer to use foldl 'instead of other options (foldl, foldr)?

+4
source

More articles:


All Articles