In Haskell, what's the difference between using takeWhile or using a "regular" inequality in this list comprehension?

Question

I'm trying to learn me a Haskell (for great good), and one of the many different things I'm doing is trying to tackle some Project Euler problems as I'm going along to test my mettle.

In doing some of the Fibonacci based problems, I stumbled on and started playing around with the recursive infinite list version of the Fibonacci sequence:

fibs = 1 : 2 : zipWith (+) fibs (tail fibs)

For one of the PE problems, I needed to extract the subsequence of even Fibonacci numbers less than 4,000,000. I decided to do this with a list comprehension, and in my playing around with the code I stumbled on to something that I don't quite understand; I'm assuming that it's my weak grasp on Haskell's lazy evaluation scheme that's complicating things.

The following comprehension works just fine:

[x | x <- takeWhile (<= 4000000) fibs, even x]

The next comprehension spins forever; so I went through and had the output returned to stdout and while it stops at the correct place, it just seems to continue evaluating the recursively defined list forever without finishing after reaching the capped value; indicative of the fact that the last item in the list is printed with a comma but no further list items or closing square bracket are present:

[x | x <- fibs, x <= 4000000, even x]

So what exactly is the secret sauce used by the various functions that do play well with infinite lists?

Answer 1

The function takeWhile keeps taking elements of the input list until it reaches the first element that doesn't satisfy the predicate, and then it stops. As long as there is at least one element that doesn't satisfy the predicate, takeWhile turns infinite lists into finite lists.

Your first expression says

Keep taking elements of this infinite list until you find one greater than 4,000,000 and then stop. Include each element in the output if it's even.

The second expression says

Keep taking elements of this infinite list. Include each element in the output if it's less than or equal 4,000,000 and it's even.

When you observe an output that hangs forever, the function is busily generating more fibonacci numbers and checking to see if they're less than or equal 4,000,000. None of them are, which is why nothing is printed to the screen, but the function has no way of knowing that it's not going to encounter a small number a bit further down the list, so it has to keep checking.