Learning Haskell: Seemingly Circular Program - Please help explain

Question

I'm currently going through the book "The Haskell Road to Logic, Math, and Programming" by Doets and Van Eijck. I've never been exposed to any functional programming language until this book, so keep that in mind.

Still early in the book, it gives the following code for a primality test:

ldp :: Integer -> Integer
ldp n = ldpf primes1 n

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p 
              | p^2 > n      = n
              | otherwise    = ldpf ps n

primes1 :: [Integer]
primes1 = 2 : filter prime [3..]

prime :: Integer -> Bool
prime n | n < 1     = error "not a positive integer"
        | n == 1    = False 
        | otherwise = ldp n == n

There is a seemingly circular programming going on in that ldp calls primes1, which calls prime, which calls ldp again. While the book does offer this as an explanation as to why the program executes and terminates:

ldp makes a call to primes1, the list of prime numbers. This is a first illustration of a ‘lazy list’. The list is called ‘lazy’ because we compute only the part of the list that we need for further processing. To define primes1 we need a test for primality, but that test is itself defined in terms of the function LD, which in turn refers to primes1. We seem to be running around in a circle. This circle can be made non-vicious by avoiding the primality test for 2. If it is given that 2 is prime, then we can use the primality of 2 in the LD check that 3 is prime, and so on, and we are up and running

While I think I understand this explanation, I would greatly appreciate it if someone could explain in laymen's terms:

1. What a "lazy list" is and how it applies in this context?
2. How knowing that 2 is prime allows the program to be non-vicious?

Any answers are greatly appreciated.

Answer 1

The first thing to note is that on its own that code does nothing. It's just a bunch of mathematical expressions and it doesn't matter how circular it is until we try to extract some values from them. How do we do that?

We could do:

print $ take 1 primes1

There's no problem here. We can take the first value of primes1 without looking at any of the recursive code, it's there explicitly as 2. What about:

print $ take 3 primes1

Let's try expanding primes1 to get some values out. To keep these expressions manageable, I'm now ignoring the print and take parts, but remember that we're only doing this work because of them. primes1 is:

primes1 = 2 : filter prime [3..]

We have our first value, and the first step to our second is expanding filter. If this were a strict language we would try to expand [3..] first and get stuck. A possible definition of filter is:

filter f (x:xs) = if f x then x : filter f xs else filter f xs

which gives:

primes1 = 2 : if prime 3 then 3 : filter prime [4..] else filter prime [4..]

Our next step has to be figuring out if prime 3 is true or false, so let's expand it using our definitions of prime, ldp and ldpf.

primes1 = 2 : if ldp 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : if ldpf primes1 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

Now, things get interesting, primes1 references itself and ldpf needs the first value to do its calculation. Luckily, we can get the first value easily.

primes1 = 2 : if ldpf (2 : tail primes) 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

Now, we apply the guard clauses in ldpf and find 2^2 > 3, therefore ldpf (2 : tail primes) 3 = 3.

primes1 = 2 : if 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : 3 : filter prime [4..] 

We now have our second value. Note that the right hand side of our evaluation never grew especially large and that we never needed to follow the recursive loop very far.

primes1 = 2 : 3 : if prime 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldp 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf primes1 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf (2 : tail primes1) 4 == 4 then 4 : filter prime [5..] else filter prime [5..]

We use the guard clause rem 4 2 == 0, therefore we get 2 here.

primes1 = 2 : 3 : if 2 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : filter prime [5..]
primes1 = 2 : 3 : if prime 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldp 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf primes1 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (2 : tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

No guard matches, so we recurse:

primes1 = 2 : 3 : if ldpf (tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (3 : tail (tail primes)) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

Now 3^2 > 5 so that expression is 5.

primes1 = 2 : 3 : if 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : 5 : filter prime [6..]

We only need three values, so evaluation can stop.

So, now to answer your questions. A lazy list is one that only requires us to evaluate what we need, and the 2 helps because it ensures that when we reach the recursive step we always have enough values already calculated. (Imagine expanding that expression if we didn't know the 2, we'd end up stuck in a loop pretty quickly.)