how to solve "stack space overflow" in haskell

Question

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

It's the difficult with any functional language. As a smart bloke I know once said every abstraction is leaky. Functional languages are great for expressing yourself and showing an algorithm will complete correctly but they all have to assume that they have infinite memory. Welcome to the world of fitting your beautiful program into a real computer... — Spence
– Spence, Commented Aug 18, 2009 at 7:32

yairchu · Accepted Answer · 2018-08-16 17:15:25Z

11

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

edited Aug 16, 2018 at 17:15

answered Aug 18, 2009 at 9:31

yairchu

25k7 gold badges72 silver badges117 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ruifeng Xie Over a year ago

It seems that you should remove the = in the first line of step.

pierrotlefou · Accepted Answer · 2009-08-18 07:27:31Z

4

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, should that suggest we should always prefer to use foldl' instead of other variants(foldl,foldr)?

answered Aug 18, 2009 at 7:27

pierrotlefou

41k39 gold badges140 silver badges176 bronze badges

Collectives™ on Stack Overflow

how to solve "stack space overflow" in haskell

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related