Monday, January 23, 2017

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 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


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.

A flashback and analogy

You've probably heard about how the notion of sum types (e.g. Algol 68 union s, Rust enum s, Haskell type s) and product types (e.g. tup...