[Haskell-cafe] help understanding lazy evaluation
Ryan Ingram
ryani.spam at gmail.com
Wed Aug 22 20:39:54 EDT 2007
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:
prime n
=> factors n == [1,n]
=> factors n == 1 : n : [] -- remove syntactical sugar from the list
=> [x | x <- [1..n], n `mod` x == 0] == 1 : n : []
=>* 1 : [x | x <- [2..n], n `mod` x == 0] == 1 : n : [] -- n mod 1 is always
0
=> 1 == 1 && [x | x <- [2..n], n `mod` x == 0] == n : []
=> True && [x | x <- [2..n], n `mod` x == 0] == n : []
=> [x | x <- [2..n], n `mod` x == 0] == n : []
This much computation happens for every single n. One of two things happens
here; either we have another factor < N, or we don't.
Case 1: There is at least one other factor < n. Let z be the smallest such
factor:
=>* z : [x | x <- [(z+1)..n], n `mod` x == 0] == n : []
=> z == n && [x | x <- [(z+1)..n], n `mod` x == 0] == []
=> False && [x | x <- [(z+1)..n], n `mod` x == 0] == []
=> False
Case 2: There are no other factors < n.
=>* n : [x | x <- [], n `mod` x == 0] == n : []
=> n == n && [x | x <- [], n `mod` x == 0] == []
=> True && [x | x <- [], n `mod` x == 0] == []
=> [x | x <- [], n `mod` x == 0] == []
=> [] == []
=> True
Exercise: Annotate each line in the above trace with a description of why
the reduction is valid.
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:
[x | x <- [1..n], n `mod` x == 0] =>
concatMap ok [1..n]
where ok x = if n `mod` x == 0 then [x] else []
concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f [] = []
concatMap f (x:xs) = f x ++ concatMap f xs
(++) :: [a] -> [a] -> [a]
(x:xs) ++ ys = x : (xs ++ ys)
[] ++ ys = ys
(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False
(==) :: [Int] -> [Int] -> Bool -- specialized via typeclass "Eq [Int]"
(x:xs) == (y:ys) = x == y && xs == ys
[] == [] = True
_ == _ = False
All other functions used are primitives.
Exercise: Write out a full execution trace for n == 3 and n == 4 with the
desugaring and Prelude functions given above.
On 8/22/07, Xavier Noria <fxn at hashref.com> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070822/46841c4f/attachment.htm
More information about the Haskell-Cafe
mailing list