Finding Elegance in Functional Programming

There is a certain elegance that I've found with my explorations with functional programming and Haskell. My plan is to take these learnings and apply them to the .NET world -- most likely with F#, but also by taking better advantage of the functional parts of C#.

I'm all about using the right tool for the job. This is why I get discouraged when I see zealots who say that we should always use a certain programming paradigm or a particular language. (You can see here for a rather humorous take on this: Why [Programming Language X] Is Unambiguously Better than [Programming Language Y]).

Euler Problems
I've talked about Euler problems previously. These are mathematical problems that really lend themselves to functional solutions. It's really easy to build up a solution by breaking the problem down into discrete pieces and adding the functionality step by step.

So, let's take a look at Euler problem #2. This is not very complicated, but it does have quite a few steps.

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-valued terms.

The first step of this problem is to generate a Fibonacci sequence. Lucky for us, we have a good function for that. We have the Fibonacci sequence itself:

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

And we have a separate function that uses a list comprehension to create a limited sequence:

testFibs = [x | x <- takeWhile (<= 21) fibs]

Let's combine these into a single function:

testFibs = [x | x <- takeWhile (<= 21) fibs]
  where
    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

We've rolled in the "fibs" definition into our "testFibs" function. The overall result is that we have a list comprehension that provides us with Fibonacci numbers as long as the values are less than or equal to 21. And here's the output:

[1,1,2,3,5,8,13,21]

Now, one issue with the Euler problem is that it defines the Fibonacci sequence a little bit differently from what we have here. Most Fibonacci sequence implementations start with 1 and 1 (resulting in 1, 1, 2, 3, 5, 8...) or with 0 and 1 (resulting in 0, 1, 1, 2, 3, 5, 8...). This example specifies starting with 1 and 2.

We technically don't need to account for this discrepancy because the problem also specifies that we want "even-valued terms", so the leading "1" would be excluded. But we can also update our "fibs" function to account for this:

testFibs = [x | x <- takeWhile (<= 21) fibs]
  where
    fibs = 1 : 2 : zipWith (+) fibs (tail fibs)

Which gives us this updated sequence: [1,2,3,5,8,13,21]

An Elegant Solution
Just to show how elegant a functional solution can be, let's walk through the process of building up our function. We'll break it down into the following parts:

1. Fibonacci sequence whose values do not exceed 4 million
2. Even-valued terms
3. Sum

We already have a function that gives us terms that do not exceed 21, so changing this to not exceed four million is pretty easy:

testFibs = [x | x <- takeWhile (<= 4000000) fibs]
  where
    fibs = 1 : 2 : zipWith (+) fibs (tail fibs)

And the result:

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578]

Now, we just need to add an additional filter to only pick out the even values. I say "additional filter" because the "takeWhile" function is a filter that limits the "fibs" sequence to a finite set of values. Lucky for us, Haskell has an "even" function built in.

testFibs = [x | x <- takeWhile (<= 4000000) fibs, even x]
  where
    fibs = 1 : 2 : zipWith (+) fibs (tail fibs)

And the result:

[2,8,34,144,610,2584,10946,46368,196418,832040,3524578]

This cuts the sequence down quite a bit.

Our last step is to simply sum up the values. Let's rename the function as well:

euler2 = sum [x | x <- takeWhile (<= 4000000) fibs, even x]
  where
    fibs = 1 : 2 : zipWith (+) fibs (tail fibs)

And this gives us the answer:

4613732

And we know this is correct by asking the internet for the solution to Euler Problem #2.

Wrap Up
There's a certain amount of elegance to this solution. We have built up a solution using several smaller functions, including "fibs", "takeWhile", "even", and "sum". Each function is responsible for doing a single thing. And we combine these small units to create more complex, useful functions.

So, as you can tell, I'm becoming a fan of functional programming. But we want to make sure that we're using the right tool for the job. Is functional programming the right solution for every problem? Absolutely not. But there are some problems (such as the one we looked at here) that really lend themselves to a functional solution. The same code written imperatively would be much more complex.

But we can take these functional solutions and apply them to a more general-purpose language like C#. At its heart, C# is an imperative language that has its roots in object-oriented programming. But it has also had many functional features added on over the years. We can start to "think functionally" and use those features more effectively. And if those features fall short, we also have the option of using F#, a .NET language built from the beginning as a functional language.

I always want to use the right tool for the job. And that means learning about as many tools as possible and figuring out where they fit in the toolbox.

Happy Coding!