[Haskell-cafe] help understanding lazy evaluation

[Xavier Noria]

I am learning Haskell with "Programming in Haskell" (an excellent  
book BTW).

I have background in several languages but none of them has lazy  
evaluation. By now I am getting along with the intuitive idea that  
things are not evaluated until needed, but there's an example I don't  
understand (which means the intuitive idea needs some revision :-).

We have factors(), defined on page 39 like this[*]:

   factors :: Int -> [Int]
   factors n = [x | x <- [1..n], n `mod` x == 0]

and we base prime() on it this way:

   prime :: Int -> Bool
   prime n = factors n == [1, n]

Now, the books says prime does not necessarily compute all of the  
factors of n because of lazy evaluation. Meaning that if n is  
composite as soon as some non-trivial divisor appears we halt  
computation and return False.

My vague intuition said "we either need factors or we don't, we do  
because we need to perform the test, so we compute it". That's wrong,  
so a posteriori the explanation must be something like this:

1. someone knows we want factor() to perform an equality test

2. someone knows an equality test between lists is False as soon as  
we have a mismatch, left to right

3. thus, instead of evaluating factors completely we are going to  
build sublists of the result and perform the tests on those ones  
against [1, n].

That's a lot of *context* about that particular evaluation of  
factors, in particular step puzzles me. Can anyone explain how lazy  
evaluation fits there? I suspect the key is the implementation of ==  
together with the fact that list comprehensions are lazy themselves,  
is that right?

-- fxn

[*] Which notation do you use for functions in text? is f() ok?