How to filter an infinite list in Haskell [duplicate]

Question

Possible Duplicate:
Finite comprehension of an infinite list

I can't understand why ghci can't compute this code correctly?

[x | x <- [1..], x < 1000]

Ghci just stops at last number and I need to interrupt this process in command line to get back to normal state. What's wrong? I expect that this code should work because of haskell's lazy evaluation.

Answer 1

[x | x <- [1..], x < 1000] is equivalent to filter (< 1000) [1..]; you want takeWhile (< 1000) [1..] instead.

So what's the difference between filter and takeWhile?

Well, if you try to evaluate the entire result --- and that's what ghci does, in order to print it --- then filter will test each and every element in the input list to determine whether it should be in the output list. After the first thousand elements? It carries on testing. filter doesn't know that it isn't suddenly going to encounter ..., 12345, 12346, -7, 12348, ....

Another way of looking at it is that filter can only say "the output list ends here" once it's reached the end of the input list. If you feed it an infinite list, it can never be sure it has generated all elements of the output list. So it will appear to hang.

takeWhile, on the other hand, stops and terminates its output list as soon as it reaches an element that fails the condition.

Answer 2

You've simply asked for every number less than 1000 in a list. You know that the list is sorted, but your algorithm doesn't take advantage of this. The compiler does not automatically realize you're working with sorted data, and cannot infer that once you've seen a number that is at least 1000, you can never again see one that is less than that.

As others have pointed out, takeWhile (< 1000) [1..] leverages your knowledge of how special your list is by specifially stopping its examination of the list once the predicate has failed for an element (in this case, once a number that is at least 1000 has been encountered). Notice how this is an optimization available because [1..] isn't "just a list"; it's a list with special properties (in particular, it's sorted).