foldr resulting in stack overflow

Question

I'm trying to generate primes using the Sieve of Eratosthenes algorithm on an infinite list. I've heard that foldr will examine the list lazily, but every time I try to use the following algorithm I get a stack overflow exception:

getPrimes :: [Int]
getPrimes = foldr getNextPrime [2] [3,5..]
    where
        getNextPrime n primes
            | not $ isAnyDivisibleBy primes n = primes ++ [n]
            | otherwise = primes
        isAnyDivisibleBy primes n = any (\x -> isDivisibleBy n x) primes
        isDivisibleBy x y = x `mod` y == 0

example:

takeWhile (\x -> x < 10) getPrimes
*** Exception: stack overflow

Somewhere the list is getting evaluated, but I can't figure out where.

That title can be read in two ways ;)

ThreeFx
– ThreeFx

2015-03-18 19:45:50 +00:00
Commented Mar 18, 2015 at 19:45 — ThreeFx
– ThreeFx, Commented Mar 18, 2015 at 19:45

dfeuer · Accepted Answer · 2015-03-18 18:41:24Z

3

I think the foldr is confusing you, so let's write it out with explicit recursion:

getPrimes :: [Int]
getPrimes = getPrimesUsing [3,5..]

getPrimesUsing :: [Int]->[Int]
getPrimesUsing [] = [2]
getPrimesUsing (n:primes)
  | not $ isAnyDivisibleBy primes n = primes ++ [n]
  | otherwise = primes
  where
    primes = getPrimesUsing primes
    isAnyDivisibleBy primes n = any (\x -> isDivisibleBy n x) primes
    isDivisibleBy x y = x `mod` y == 0

Can you see the trouble now?

An unrelated point: the algorithm you seem to be trying to implement here is not the Sieve of Eratosthenes, but rather a much less efficient algorithm called trial division.

answered Mar 18, 2015 at 18:41

dfeuer

48.8k5 gold badges69 silver badges171 bronze badges

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

Comments

András Kovács · Accepted Answer · 2015-03-18 18:43:12Z

2

foldr getNextPrime [2] [3, 5 .. ] expands to:

(getNextPrime 3 (getNextPrime 5 (getNextPrime 7 ...

Since getNextPrime always needs to inspect its second argument, we just get a non-terminating chain of getNextPrime calls, and the initial [2] list is never used.

answered Mar 18, 2015 at 18:43

András Kovács

30.2k3 gold badges56 silver badges103 bronze badges

Comments

bheklilr · Accepted Answer · 2015-03-18 18:45:27Z

foldr is defined as

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

So when you plug in the arguments you would get

foldr getNextPrime [2] [3,5..]
    = getNextPrime 3 (foldr getNextPrime [2] [5,7..])
    = getNextPrime 3 (getNextPrime 5 (foldr getNextPrime [2] [7,9..])
    etc...

For this to lazily produce values (what you want when dealing with infinite lists) then getNextPrime needs to lazily produce values. Looking at the definition of getNextPrime, primes ++ [n], meaning you're appending a value onto the end of your primes list, but primes for getNextPrime 3 is getNextPrime 5 (foldr getNextPrime [2] [7,9..]). But then primes for getNextPrime 5 is getNextPrime 7 (foldr getNextPrime [2] [9,11..]), etc, etc. You never actually are able to produce a normal form value for primes, it's always a chain of computations that never return.

Another way to look at this is to look at this is to replace getNextPrime with an operator, let's call it .:

foldr (.:) [2] [3,5..9]
    = 3 .: (5 .: (7 .: (9 .: [2])))

(this is why it's called a right fold, the parens are nested to the right)

This works great for using : in foldr:

foldr (:) [2] [3,5..9]
    = 3 : (5 : (7 : (9 : [2])

because : just builds a new data structure, and the first element of this data structure can be inspected without calculating the rest of the structure. But .: isn't so nice, it first needs to calculate x1 = 9 .: [2], then x2 = 7 .: x1, then x3 = 5 .: x2, and finally 3 .: x3. For [3,5..] instead, you never can calculate the last call of something .: [2], but haskell keeps trying to compute it and that blows the stack.

Collectives™ on Stack Overflow

foldr resulting in stack overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related