Haskell recursive list comprehension causes C Stack Overflow

Question

So I'm making a list of prime numbers to help me learn haskell using simple trial division (no fancy stuff until I get better with the language). I'm trying to use the following code:

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]

This is loaded without an error. However:

>take 2 primes
[2ERROR - C stack overflow

I tried the same thing with nested list comprehensions. It doesn't work. I would guess that I'm making too many recursive calls, but this shouldn't be the case if i'm only computing one prime. In my mind the lazy evaluation should make it so that take 2 primes does something along the lines of:

primes = 2 : [ 3 | all (\p -> (mod 3 p) /= 0) [2] ]

Which doesn't require all that much computation - mod 3 2 == True, so all (\p -> (mod 3 p) /= 0) == True, which means take 2 primes == [2, 3], right? I don't understand why this isn't working. Hopefully someone much more versed in the black magic of functional programming can help me...

This is on HUGS, if that makes any difference.

EDIT- I was able to come up with this solution (not pretty):

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) (takeWhile (<= (ceiling (sqrt (fromIntegral x)))) primes)]

EDIT2- The program works fine when interpreted through HUGS or GHCi, but when I try to compile it with GHC, it outputs test: <<loop>>. Anybody know what the problem is?

Answer 1

Hugs shouldn't do this, but the code is broken anyway so it doesn't matter. Consider:

primes = 2 : [ x | x <- [3..], all (\p -> (mod x p) /= 0) primes]

How do you determine if 3 is prime? well, does mod 3 2 == 0? No. Does mod 3 ??? == 0? OOPS! What is the next element of primes after two? we don't know, we are trying to compute it. You need to add an ordering constraint that adds 3 (or any other x) once all p elem primes less than sqrt x have been tested.

Answer 2

The documentation for all says "For the result to be True, the list must be finite" http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:all

Answer 3

The previous answers explained why the original comprehension didn't work, but not how to write one that would work.

Here is a list comprehension that recursively, lazily (albeit not efficiently) computes all primes:

let primes = [x | x <- 2:[3,5..], x == 2 || not (contains (\p -> 0 == (mod x p)) (takeWhile (\b -> (b * b) < x) primes))]

Obviously we don't need to check mod x p for all primes, we only need to do it for primes less than the sqrt of the potential prime. That's what the takeWhile is for. Forgive the (\b -> (b * b) < x) this should be equivalent to (< sqrt x) but the Haskell type system didn't like that.

The x == 2 prevents the takeWhile from executing at all before we've added any elements to the list.