Project Euler

Project Euler # 2

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s