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.

Jordan

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.)

Eckhart

Answer 2

In order:

Laziness is the property of only evaluating expressions as you need to, rather than when you possibly could. A lazy list is one which could possibly be infinite. Obviously attempting to evaluate an infinite list would be a bad idea if the evaluation were not lazy.

I'm not sure what "non-vicious" means, but I think you'll find that having the value "2" as a known prime provides a base case for the recursion, i.e. it provides a particular input upon which the program will terminate. Writing a recursive function (or indeed a set of mutually recursive functions) usually involves reducing some input value towards this base case in successive steps of application.

For reference, program fragments of this shape are usually called mutually recursive. The term "circular reference" is not one you'd really apply in this case.

Numerary

a vicious circle is is one where unpleasantness is passed around, e.g. boy1 bullies boy2, boy2 tells his father who gets upset and is mean to his employees, one of whom is father of boy1 who then takes his frustration out on his son, who then bullies boy2... A non-vicious circle is a cycle that doesn't carry unpleasantness around. – Exerciser

Right, I'm familiar with the term in other contexts, but I've never seen it applied to analysis of programs. Is this a haskellism I'm not familiar with? – Numerary

It's not a Haskell-ism. 'vicious circle' is an English language idiom (whether it is exclusive to English, I don't know). Any circular sequence of events (whether in life or in programming) that you would wish not to be circular could be termed a 'vicious circle'. – Tereus

Right. I didn't notice that the quoted text used the term as well. I thought this was maybe something that the OP had dreamed up to describe the situation. I don't think it's a very helpful term, in any case. "Non-terminating", "diverging", or an "infinite loop" would all be terms that I would readily associate with this concept, however :) – Numerary

Answer 3

One defining feature of Haskell is its laziness. Lists are only part of that story. Basically, Haskell never performs any calculation until:

1. the value of the calculation is required to calculate something else that is required to...
2. you told Haskell to calculate something sooner than it otherwise might.

So the primes1 function produces a list of Integer values, but it doesn't produce any more than is necessary to satisfy the overall calculation. Even so, if you defined it this way:

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

you would have a problem. primes1 would attempt to generate the first value in its sequence by (indirectly) evaluating prime 2, which would evaluate ldp 2, which would ask for the first value produced by primes1...presto infinite loop!

By directly returning 2 as the first value of the sequence generated by primes1, you avoid the infinite loop. For each subsequent value generated in the sequence, primes1 has already generated a previous value that will be evaluated by ldp as part of calculating the subsequent value.

Tereus