<div>The insight is that the functions called can be lazy internally; the computation doesn't proceed by either fully evaluating something or not, but rather by rewriting parts of the computation graph. Here is a trace of the evaluation of "prime" for integers n > 1:
</div>
<div> </div>
<div>prime n</div>
<div>=> factors n == [1,n]</div>
<div>=> factors n == 1 : n : [] -- remove syntactical sugar from the list</div>
<div>=> [x | x <- [1..n], n `mod` x == 0] == 1 : n : []</div>
<div>=>* 1 : [x | x <- [2..n], n `mod` x == 0] == 1 : n : [] -- n mod 1 is always 0</div>
<div>=> 1 == 1 && [x | x <- [2..n], n `mod` x == 0] == n : []</div>
<div>=> True && [x | x <- [2..n], n `mod` x == 0] == n : []</div>
<div>=> [x | x <- [2..n], n `mod` x == 0] == n : []</div>
<div> </div>
<div>This much computation happens for every single n. One of two things happens here; either we have another factor < N, or we don't.</div>
<div> </div>
<div>Case 1: There is at least one other factor < n. Let z be the smallest such factor:</div>
<div>=>* z : [x | x <- [(z+1)..n], n `mod` x == 0] == n : []</div>
<div>=> z == n && [x | x <- [(z+1)..n], n `mod` x == 0] == []</div>
<div>=> False && [x | x <- [(z+1)..n], n `mod` x == 0] == []</div>
<div>=> False</div>
<div> </div>
<div>Case 2: There are no other factors < n.</div>
<div>=>* n : [x | x <- [], n `mod` x == 0] == n : []</div>
<div>=> n == n && [x | x <- [], n `mod` x == 0] == []</div>
<div>=> True && [x | x <- [], n `mod` x == 0] == []</div>
<div>=> [x | x <- [], n `mod` x == 0] == []</div>
<div>=> [] == []</div>
<div>=> True</div>
<div> </div>
<div>Exercise: Annotate each line in the above trace with a description of why the reduction is valid.</div>
<div> </div>
<div>To be totally clear with this trace, you would need to desguar the list comprehension and some of the more primitive functions. The lines marked with =>* are a bit handwavy because they skip evaluation. Here's the desugaring of this list comprehension and full definitions of the other functions in used in this example:
</div>
<div> </div>
<div>[x | x <- [1..n], n `mod` x == 0] =></div>
<div> concatMap ok [1..n]</div>
<div> where ok x = if n `mod` x == 0 then [x] else []</div>
<div> </div>
<div>concatMap :: (a -> [b]) -> [a] -> [b]</div>
<div>concatMap f [] = []</div>
<div>concatMap f (x:xs) = f x ++ concatMap f xs</div>
<div> </div>
<div>
<div>(++) :: [a] -> [a] -> [a]</div>
<div>
<div>(x:xs) ++ ys = x : (xs ++ ys)</div>[] ++ ys = ys</div>
<div> </div>(&&) :: Bool -> Bool -> Bool</div>
<div>True && x = x</div>
<div>False && _ = False</div>
<div> </div>
<div>(==) :: [Int] -> [Int] -> Bool -- specialized via typeclass "Eq [Int]"</div>
<div>(x:xs) == (y:ys) = x == y && xs == ys</div>
<div>[] == [] = True</div>
<div>_ == _ = False</div>
<div> </div>
<div>All other functions used are primitives.</div>
<div> </div>
<div>Exercise: Write out a full execution trace for n == 3 and n == 4 with the desugaring and Prelude functions given above.</div>
<div> </div>
<div><span class="gmail_quote">On 8/22/07, <b class="gmail_sendername">Xavier Noria</b> <<a href="mailto:fxn@hashref.com">fxn@hashref.com</a>> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">I am learning Haskell with "Programming in Haskell" (an excellent<br>book BTW).<br><br>I have background in several languages but none of them has lazy
<br>evaluation. By now I am getting along with the intuitive idea that<br>things are not evaluated until needed, but there's an example I don't<br>understand (which means the intuitive idea needs some revision :-).
<br><br>We have factors(), defined on page 39 like this[*]:<br><br> factors :: Int -> [Int]<br> factors n = [x | x <- [1..n], n `mod` x == 0]<br><br>and we base prime() on it this way:<br><br> prime :: Int -> Bool
<br> prime n = factors n == [1, n]<br><br>Now, the books says prime does not necessarily compute all of the<br>factors of n because of lazy evaluation. Meaning that if n is<br>composite as soon as some non-trivial divisor appears we halt
<br>computation and return False.<br><br>My vague intuition said "we either need factors or we don't, we do<br>because we need to perform the test, so we compute it". That's wrong,<br>so a posteriori the explanation must be something like this:
<br><br>1. someone knows we want factor() to perform an equality test<br><br>2. someone knows an equality test between lists is False as soon as<br>we have a mismatch, left to right<br><br>3. thus, instead of evaluating factors completely we are going to
<br>build sublists of the result and perform the tests on those ones<br>against [1, n].<br><br>That's a lot of *context* about that particular evaluation of<br>factors, in particular step puzzles me. Can anyone explain how lazy
<br>evaluation fits there? I suspect the key is the implementation of ==<br>together with the fact that list comprehensions are lazy themselves,<br>is that right?<br><br>-- fxn<br><br>[*] Which notation do you use for functions in text? is f() ok?
<br><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe">
http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></blockquote></div><br>