[Haskell-cafe] help understanding lazy evaluation

[Neil Mitchell]

Hi

>    factors :: Int -> [Int]
>    factors n = [x | x <- [1..n], n `mod` x == 0]
>
>    prime :: Int -> Bool
>    prime n = factors n == [1, n]
>
> 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:

The key point is that factors doesn't either compute all or none, it
may compute part of the value. It does this by computing something
like:

_:_
1:_
1:_:_

where _ is the unevaluated bit, i.e. it computes one bit of the result
at a time.

Equals also has this property, it can be defined as:

a:as == b:bs = a == b && as == bs
[] == [] = True
_ == _ = False

If you have (1:_) == (2:_) then the match will fail instantly.

> 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?

Everything is lazy, to all subparts. You might get along better with a
reasoning more of the form "to compute anything, this expression will
demand this expression" - rather than your "someone knows we'll need".
If you follow example derivations you'll see that there is always a
very clear idea of what needs to happen next for the computation to
proceed, which explains the laziness quite naturally.

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

Sure, although a little unusual for Haskell where f() means f applied
to the empty tuple. Some people use |f| (generally those who use
latex), but generally it can be inferred from the context what is a
function

Thanks

Neil