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