[Haskell-cafe] help understanding lazy evaluation

Neil Mitchell ndmitchell at gmail.com
Wed Aug 22 19:28:49 EDT 2007


>    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


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



More information about the Haskell-Cafe mailing list