[Haskell-cafe] help understanding lazy evaluation

[Michael Vanier]

Xavier,

First off, we don't put the () after function names in Haskell.

What's happening is this (experts please correct any mistakes here):

1) You call prime on a number (e.g. 42).

2) In order to evaluate this further, (factors 42) must be evaluated at least
partially to give input to == in prime.  So (factors 42) is evaluated to give the first list value,
which is 1.

3) The == in prime compares the 1 at the head of the list generated by (factors 42) (whose tail
hasn't been evaluated yet) with the 1 at the head of [1, 42], and finds that they match, so == can
continue processing.

4) (factors 42) resumes to compute another list value, which is 2 (a factor of 42).

5) == in prime compares 2 with 42, finds they don't match, and thus (primes 42) returns False.

So not all the factors have been computed; in fact, only two of them were needed to prove that 42 is
not prime.  The interesting aspect of all this is that laziness allowed us to modularize the problem
of primality testing into two separate (simpler) functions, instead of having to interleave
generation of factors and testing of factors.  This makes code easier to write and more modular.
Hughes' paper "Why Functional Programming Matters" is a must-read for more on this.

Lazy evaluation can be very tricky to wrap your head around, and there are lots of subtle issues
that crop up where you think something is lazy but it's not, or you think something is strict but
it's not.  There are ways to force lazy/strict behavior, but they're somewhat more advanced.

HTH,

Mike


Xavier Noria wrote:
> 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?
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe