Project Euler # 2: **Even Fibonacci numbers**

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the fibonacci sequence whose values do not exceed four million, find the sum of the even-value terms.

My approach in Python:

Includes a recursive function to generate a finite set of fibonacci numbers, which are then summed within a generator expression.

LOC: 7 lines

My approach in Haskell:

Uses a recursive function to generate an infinite set of fibonacci numbers, which are filtered and summed within a list comprehension.

LOC: 3

**Optimisation Discussion:**

I find this Project Euler challenge really interesting. Some of the later challenges require you to find “optimal” or “near-optimal” solutions because the naive solution is just so slow. However, this isn’t really the case here. There are certainly more optimal solutions:

- sum the entire fibonacci sequence (below 4,000,000 limit) and halve it
- sum every third term in the fibonacci sequence
- certain mathematical fibonacci generators

However, only 33 terms exist beneath the 4,000,000 limit. With this in mind, there is little *practical* advantage to optimisation. And this, IMHO, is the most interesting thing in this challenge: the balance between elegance and practicality. In most situations I lean towards the former, there is beauty in finding more elegant solutions.

**Python vs. Haskell Discussion:**

Both the Python and Haskell versions use recursion to build the fibonacci sequence. The biggest difference is that Python requires a base case to terminate the recursive function – where Haskell’s lazy evaluation is perfectly happy with an infinite series. I think this is quite incredible! Haskell powerfully changes the conceptual nature of our programming.

I have read so much about how succinct Haskell programs are, and this is a great example – where the Haskell version is half the length of the recursive Python version. It is the need for a base case in Python recursion that blows out the line count. But can we do without it?

**Python Generators**

We can shrink the Python code length, and use functional programming concepts (generators) to modify the Python function to something that is conceptually similar to the Haskell version: Reduces the line count to 5 lines, and I love the way it takes advantage of lazy evaluation. It is also much cleaner to read and maintain. I would even go as far as saying that it is more “memory friendly” than the Haskell version, since the Haskell version builds a list in memory, but this new Python does not, it is entirely ‘in-place’. Of course, the scope of the fibonacci list in Haskell is strictly local and is returned immediately, so there is no on-going overhead.

So that ends my discussion on Project Euler # 2. I very much like the readability of the alternative Python solution. But it requires understanding of functional concepts, which an OOP-centered programmer may not necessarily grasp. Overall then, I think I prefer the Haskell implementation, as it is entirely “native” to Haskell and is supremely elegent in just 2 lines of code (+ a type declaration for good measure).