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!

Learning from Haskell (Preview)

I really want to talk about the cool take-aways I got from exploring Haskell. But I want to put this off for just a little bit. The reason is that I went from reading Learn You as Haskell for Great Good! (review) straight into Parallel Programming with Microsoft .NET, a book from the Microsoft Patterns and Practices team (available to read online).

I've heard people talk about how functional programming is a good match for parallel programming, and I'm really seeing that as I read through the recommendations and patterns in the Parallel Programming book. These are things like immutability, avoiding updates to shared objects, repeatability, and the ability to break things up into practical chunks. And I've seen these features in my exploration of Haskell.

So, I'm going to hold off talking about cool things like "Maybe" and higher-order functions until after I finish the latest book. That way, I'll be able to show exactly how these types of things help with parallel programming.

An interesting note about Parallel Programming with Microsoft .NET: the technologies include the Task Parallel Library (TPL) and PLINQ. And LINQ/PLINQ are very functional technologies that have been included in .NET. I'm a huge fan of LINQ, and I've been exploring this for a while.

So, stay tuned, and I'll have some good stuff in a couple of weeks.

Happy Coding!

A Functional Fibonacci Sequence (as Learned by an Imperative Programmer)

As mentioned previously, I've been interested in learning different programming languages and paradigms, not necessarily so that I can program in those languages, but so that I can improve my everyday programming in my main language.

One of my favorite things to noodle around with is the Fibonacci Sequence. This is just complicated enough to be interesting but not too complicated to be overwhelming. The sequence is easy enough:

1, 1, 2, 3, 5, 8, 13, 21, ...

Each item in the sequence is created by adding the 2 previous numbers. The sequence can start with either 0 or 1 (I use the version that starts with 1). So, the sequence goes like this:

 1
 1 = 1 + 0
 2 = 1 + 1
 3 = 1 + 2
 5 = 2 + 3
 8 = 3 + 5
13 = 5 + 8
21 = you get the idea

This is a classic example of a sequence that would lend itself to a recursive function. In my example code, I calculate the sequence using some global variables, but that's usually because the focus of the example is not on the Fibonacci sequence itself but on the code that uses it.

A Recursive Implementation
When I started diving into Haskell, I thought that implementing a Fibonacci sequence would be a good way for me to get familiar with the language. My first implementation included 2 functions.

fibonacci :: Int -> Int
fibonacci 1 = 1
fibonacci 2 = 1
fibonacci n = fibonacci(n-1) + fibonacci(n-2)

This method takes a parameter for the position of the number in the sequence. So, for example, if we call "fibonacci 4", it will give us the 3rd number in the Fibonacci sequence (which is 3). It does this with a recursive call. Let's walk through the implementation above.

"fibonacci 4" would use the last case ("fibonacci n") and would result in the following:

fibonacci (4-1) + fibonacci (4-2)

Reduced to

fibonacci 3 + fibonacci 2

"fibonacci 2" is equal to "1". Let's put that in:

fibonacci 3 + 1

"fibonacci 3" will use the "fibonacci n" case. Let's expand that:

fibonacci (3-1) + fibonacci (3-2) + 1

or

fibonacci 2 + fibonacci 1 + 1

And since "fibonacci 2" equals 1 and "fibonacci 1" also equals 1, we're left with

1 + 1 + 1

So, the 4th item in the Fibonacci sequence is 3.

To create a sequence of these numbers, I created another recursive function:

fibonacciList :: Int -> [Int]
fibonacciList 1 = [1]
fibonacciList n = fibonacciList (n-1) ++ [fibonacci n]

To use this method, we just pass in the number of items in our Fibonacci sequence, and it returns a list with the specified number of items.

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

This function basically builds a list based on the "fibonacci" function. So, it creates the elements of the list by running "fibonacci 1", then "fibonacci 2", "fibonacci 3", ... "fibonacci n". We won't go through the recursion step-by-step.

A Big Problem
I was pretty proud of myself when I came up with these methods. I created a Fibonacci sequence, and I did it "functionally". But these methods have a big problem.

Since the "fibonacciList" function calls "fibonacci n" for each element, it actually ends up recalculating all of the previous numbers each time. What this means is that it works fine for small lists. But once we get to slightly larger lists, we find that the calculation slows down significantly. In fact, "fibnonacci 35" takes over 20 seconds to calculate on my laptop. That seems pretty ridiculous.

I was actually working on Euler problem #2 when I ran into this performance issue. And it really bothered me. So, I started to look for other solutions to calculate the Fibonacci sequence.

Note: I talked about Euler problems when I worked through Euler problem #1 on my blog.

A Truly Functional Fibonacci
I ran across this implementation that is very simple. But since my brain isn't quite used to thinking functionally, this completely escaped me. And when I saw the solution, it took a while before I really understood what it was doing.

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

The ":" operator basically creates list elements. So, when we have "1 : 1", this is the equivalent of the list "[1,1]". This function will actually create an infinite list of Fibonacci numbers (which is really interesting to run). We can wrap this in a list comprehension to return a list that stops once we get to 21.

testFibs = [x | x <- takeWhile (<= 21) fibs]
[1,1,2,3,5,8,13,21]

This works because Haskell is lazy evaluated. So even though the "fibs" list is infinite, Haskell will stop processing once it hits the takeWhile limitation that we set (<= 21).

Let's think about how "fibs" works. The "zipWith" function applies a function (in this case "+") to two lists. The lists are "fibs" (which is the current list) and "tail fibs" which includes everything but the first item. Again, this takes a bit to wrap your head around since these are recursive calls that are lazy evaluated.

It ends up creating a sort of ongoing offset list.

               [1, 1]
               [1]
         [1, 1, 2]

Here "fibs" is [1,1] and "tail fibs" is [1]. When we add these together (ignoring any "leftover" elements), we get [2] which is appended to the list.

            [1, 1, 2]
            [1, 2]
      [1, 1, 2, 3]

To get the 4th item, "fibs" is [1,1,2] and "tail fibs" is [1,2]. When we add these, we get [2, 3].

         [1, 1, 2, 3]
         [1, 2, 3]
   [1, 1, 2, 3, 5]

This continues, we can see that adding the columns from the diagram, fibs + tail fibs = the rest of the Fibonacci sequence.

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

Okay, so I don't know if the diagrams make it more clear or less clear. The combination of lazy evaluation with the recursiveness makes this quite a brain twister. But once it "clicks", it's extremely cool.

Wrap Up
So, what I've learned from this exercise is that I'll have to do a lot more work with functional programming for this to become more natural. I know that my first pass won't always be correct. But, I've found that solving a complex problem by building the solution up from smaller steps is a pretty amazing way to work.

I'll keep exploring functional programming (heading into F# soon), and I'm looking forward to making my brain think in new ways.

Happy Coding!

Book Review: Learn You a Haskell for Great Good!

I recently finished reading Learn You a Haskell for Great Good! by Miran Lipovača (Amazon Link). And, yes, it did take me a long time to get through this book -- mainly due to other distractions. I started reading this way back in October, got a good start, and then let it sit around for a while.

I'll split this into 2 parts -- the basics and the more advanced stuff.

The Basics
Learn You a Haskell gives a fairly gentle introduction to functional programming and the Haskell language. Lipovača understands that functional programming is an unfamiliar concept to many programmers who are starting out with Haskell. As such, he combines functional programming concepts with the description of how the various elements of the language work.

Haskell is a purely functional language, meaning that functions are first-class citizens (actually, the only citizens). And it is built around the concepts of immutability, "no side effects", and repeatability. Some other functional languages have compromises that let them fit in with more imperative programming.

I found this very helpful as a first step into functional programming. I really had to start thinking about immutability and repeatability in my own Haskell code. There is no other way of doing it.

The book takes small steps in introducing new concepts. This is very additive in nature (which is nice). And to describe some of the basics, the examples build simple functions based on prior learnings. Often, these simple functions end up as standard functions that are supplied with the standard modules. But it's nice to see how these functions actually work.

For an example, take a look at the zipWith' function (which I mentioned earlier in a different context):

This is from Chapter 5 (Higher-Order Functions) and shows several different concepts that are covered earlier. The concepts include function declaration (the first line), lists (the angle brackets), filters (the last 3 lines that work like a "case" statement), working with head/tail on lists (the "x:xs" and "y:ys"), and recursion (the "zipWith'" call in the last line).

This particular example is to add on the "higher-order function" part. A higher-order function is a function that takes another function as a parameter. In this case, the zipWith' function takes a function and 2 lists as parameters. Then it applies the function to each element of the lists and returns a list.

For example:

zipWith' (+) [1,2,3] [4,5,6]

Takes the "+" function (yes, that's really a function in Haskell) and uses it with the first element of each list, then the second element of each list, and so on. So, it calls "1 + 4", "2 + 5", and "3 + 6".  The result is a list: [5, 7, 9].

And of course, this leads to the Foo Bar example that I actually like.

The Advanced Stuff
The skill level ramps up. Lots of concepts are covered including Functors, Applicative Functors, Monoids, and Monads.

Things were a little fuzzy to me in the middle of the book. Since Lipovača uses the "building on previous knowledge" approach. I figured that I would be totally lost for the rest of the book, but I kept pressing forward.

What I found was that I was able to pick things back up again. For example, I got a bit lost in the description of applicative functors. But then, moving on to monoids, Lipovača describes how monoids build on top of applicative functors. And for some reason, reviewing the old material in conjunction with the new material made the old concept "click" with me.

Where I Explored Further
To help me get acquainted with Haskell (and functional programming in general), I took a look at the Euler problems. These are math-related problems that really lend themselves to being solved functionally. I used these to get me to start thinking functionally. I wrote about my encounter with the first Euler problem a few months back.

And I spent quite a bit of time on the second Euler problem. This deals with the Fibonacci sequence. I have a bit of fondness for the Fibonacci sequence. I have used a non-recursive implementation in C# in some of my previous examples. Since the Fibonacci sequence is often solved with a recursive function, I started there.

What I found is that creating a Fibonacci sequence with a classic recursion method is extremely slow. So, I spent some more time trying different approaches. And I found some really interesting Haskell examples online with completely different approaches. I'll talk about these in a later article.

Wrap Up
I found Learn You a Haskell for Great Good! to be a really good resource for me. It gave me a good overview of functional programming concepts. Now, I have had some exposure to functional concepts; I've been exploring them casually for the last year or so. Someone who is brand new to functional programming may need to spend a bit more effort on the early chapters. But that effort will pay off.

So, I put Learn You a Haskell for Great Good! into the "recommended" category. Check it out if you want to get started with programming in a purely functional language.

Happy Coding!

Functional Practice: Euler Problem #1

I've learned about Euler problems quite a while back. If you're not familiar with them, you can check out Project Euler.

These are very mathematically focused problems, and I was thinking about using them as practice problems for C#. Many people have done that; here's one example: http://www.mathblog.dk/project-euler-solutions/.

When I was looking at the problems, though, I always felt that my C# solutions would be a bit of a mess -- lots of if/else, while, switch, and so on. The solution is not functional or elegant (which always makes me think of this song).

But these seem like a great place to start using functional programming. Since I'm learning functional programming with Haskell, that's the language I'll use for my solutions.

Now, I'm not going to blog about all of the Euler problems (there are a lot of solutions out there). I'm just going to go over my thinking to solve the first problem. This will show how learning about functional programming will let you start to think a bit differently if you come from the OO world.

Euler Problem #1
Here's the first problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

This doesn't sound that hard. We'll start by trying to replicate the sample: the natural numbers below 10.

Thinking Functionally
What I found myself doing immediately was breaking this problem down into different parts. We need the natural numbers below a certain value. We need to find the ones that are multiples of 3. We need to find the ones that are multiples of 5. We need to sum things up.

This is a great place to use a list in Haskell.

First, let's get a list of all the natural numbers less than 10. We'll use a list comprehension with a range:

[x | x <- [1..9]]

And here's the output

[1,2,3,4,5,6,7,8,9]

That's a good start.  Now we need to filter things a bit. Let's add the modulo function (mod) to get the values evenly divisible by 3:

[x | x <- [1..9], mod x 3 == 0]

 The "mod" function takes 2 parameters. This may look a little strange, so we'll change this to use infix notation by using a backtick around the function name:

[x | x <- [1..9], x `mod` 3 == 0]

This seems a little less strange. And here's the output:

[3,6,9]

And since we want multiples of 5 along with multiples of 3, we can "or" these together with "||". Here's how that looks:

[x | x <- [1..9], x `mod` 3 == 0 || x `mod` 5 == 0]

And here's the output:

[3,5,6,9]

Success! This matches the list from the sample. Now we just have to sum these numbers. Fortunately, we can just pass a list to the "sum" function.

sum [x | x <- [1..9], x `mod` 3 == 0 || x `mod` 5 == 0]

And the output:

23

This matches the sample case. Now we just need to swap out the "below 10" for "below 1000":

sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

And the answer:

233168

Note: I've verified this is correct by looking at the answer to Euler Problem #1.

Making a Reusable Function
The last thing that I want to do is create a reusable function. (I'm not really sure what use I would have for this, but anyway...) So, let's parameterize this with the "below this number" value (ignore any line breaks you might see).

euler1 belowThis = sum [x | x <- [1..(belowThis-1)], x `mod` 3 == 0 || x `mod` 5 == 0]

Basically, we created a named function "euler1" with a parameter for our "belowThis" number. Since ranges are inclusive, we subtract one from the value before creating our original list.

Now we can use this function with the sample:

euler1 10
23

Or with the target value:

euler1 1000
233168

That's pretty cool.

To create this function, we just started with the inside and worked our way out. And this is a big difference between thinking functionally and thinking procedurally. If I were to try this with C#, I would probably just "brute force" it. You can see an example of that here: http://www.mathblog.dk/project-euler-problem-1/.

But instead, we have something functional and elegant. And also a good way to stretch a bit to learn functional programming. And I'm already starting to see how I can use these techniques to make my everyday programming (in C#) much better.

I'll leave the rest of the Euler Problems as an exercise for the reader.

Happy Coding!