Prime Number generator with recursion and list comprehension

Question

I am a newbie to Haskell programming and have trouble understanding how the below list comprehension expands.

primes = sieve [2..] 
sieve (p:xs) = p : sieve [x | x <-xs, x `mod` p /= 0]

Can someone correct me how the sieve expansion works:

• As we are pattern matching in sieve, p would associate to 2 and xs from [3..].
• Next, in the list comprehension x<-3, but then how can we call sieve with just 3 when there is no short-circuit.

Other thing I do not understand is how recursion works here.

I think it would be clear if one could expand the above one step at a time for first few numbers, say until 5.

Answer 1

Let's do some equational reasoning.

primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

The [2..] is sintactic sugar for [2, 3, 4, 5, ...] so

primes = sieve [2, 3, 4, 5, 6, ...]

Inline sieve once:

primes = 2 : sieve [x | x <- [3, 4, 5, 6, 7, ...], x `mod` 2 /= 0]

First, x gets value 3 which passes the mod 2 filter

primes = 2 : sieve (3 : [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0])

Inline sieve again (I renamed x to y to prevent confusions)

primes = 2 : 3 : sieve [y | y <- [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0], 
                            y `mod` 3 /= 0]

Now x = 4 fails the mod 2 filter but x = 5 passes it. So

primes = 2 : 3 : sieve [y | y <- 5 : [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0], 
                            y `mod` 3 /= 0]

This y = 5 also passes the mod 3 filter so now we have

primes = 2 : 3 : sieve (5 : [y | y <- [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0], 
                                 y `mod` 3 /= 0])

Expanding sieve one more time (z instead of y) gets us to

primes = 2 : 3 : 5 : sieve [z | z <- [y | y <- [x | x <- [6, 7, 8, ...], 
                                                    x `mod` 2 /= 0], 
                                          y `mod` 3 /= 0], 
                                z `mod` 5 /= 0]

And the expansion continues on the same way.