[Haskell-cafe] help understanding lazy evaluation
Neil Mitchell
ndmitchell at gmail.com
Wed Aug 22 19:28:49 EDT 2007
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
More information about the Haskell-Cafe
mailing list