### Careful with that infinite list, Eugene...

Warning: this will give away one way to solve a certain low-numbered Project Euler problem.

Any Haskell book, blog, or tutorials you come across has a good chance of including the

Thanks to laziness, it will only evaluate out to the last term we actually request... that was, long ago, my downfall. I wanted the terms no bigger than four million, so

right? Wrong. You and I know that the Fibonacci sequence is monotonically increasing, but

is the way to go.

The particular problem has an additional constraint, because it only wants the even terms of the sequence no bigger than four million. Easy enough to do, just feed it through

and you're good. It did, though, occur to me: does the order of filtering matter? I mean, just plain

is still an infinite list... but as long as we only actually evaluate finitely many values, we're safe.

and

both terminate and, as you'd expect, give the same result--but while the order doesn't matter to the result, it may matter for speed. Given that the first Fibonacci number is even and the next odd, the whole sequence is thus even, odd, odd, even, odd, odd, ... so

will only check a third as many values for being no more than four million.

Any Haskell book, blog, or tutorials you come across has a good chance of including the

*très élégant*Haskell one-liner for an infinite list containing the Fibonacci sequence:**fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))**Thanks to laziness, it will only evaluate out to the last term we actually request... that was, long ago, my downfall. I wanted the terms no bigger than four million, so

**filter (<= 4000000) fibs**right? Wrong. You and I know that the Fibonacci sequence is monotonically increasing, but

**filter**doesn't, and it doesn't even notice the particular function we're filtering with to realize it could terminate thanks to monotonicity. So instead,**takeWhile (<= 4000000) fibs**is the way to go.

The particular problem has an additional constraint, because it only wants the even terms of the sequence no bigger than four million. Easy enough to do, just feed it through

**filter even**and you're good. It did, though, occur to me: does the order of filtering matter? I mean, just plain

**filter even fibs**is still an infinite list... but as long as we only actually evaluate finitely many values, we're safe.

**filter even $ takeWhile (<= 4000000) fibs**and

**takeWhile (<= 4000000) $ filter even fibs**both terminate and, as you'd expect, give the same result--but while the order doesn't matter to the result, it may matter for speed. Given that the first Fibonacci number is even and the next odd, the whole sequence is thus even, odd, odd, even, odd, odd, ... so

**takeWhile (<= 4000000) $ filter even fibs**will only check a third as many values for being no more than four million.

## Comments