Moving to a functional state of mind with F#


In my previous post, I talked about my uneventful journey of learning a functional language and how it was revived again by discovering this great book called Functional Programming for the real world. What’s great about this book is that the authors prepare you mentally for the transition to a functional state of mind. If you are not interested in functional programming, understanding the key aspects of it is still beneficial because it opens up a different approach to solving problems, which is never a bad thing. For example, functional programmers aim to write elegant and succinct code, as well as aiming to be natural to read by making use of it’s declarative nature. Once you learn this skill, you can apply this even to static language, as we will soon see.

In F# (and other functional languages), three key elements are immutability, recursion and using functions as values. Let’s break it down….

Immutability

Immutability means that when something is assigned, it’s value can never be changed. In C#, this is done using the readonly keyword, like so..

   public readonly int someValue;

Immutability has its benefits. For instance when you perform  multi-threading and parallelism, immutability alleviates you from having to write code to prevent deadlocks and race conditions. What’s unfamiliar to most programmers quickly is that you have to create new instances of everything, no more modifying the value of a variable you declared earlier. Let’s illustrate this with a simple example with Recursion.

Recursion

To learn to be able to think functionally, understanding recursion is one of the first steps you take.  In short, a recursive function is a function that calls itself, where one branch will have a terminating condition, and the other recurse. I have not really done much recursion with imperative programming as we mostly loop all day long and I suspect that is typically the case. However most loops can be expressed with recursion (for better or worse though), with the added incentive of attaining immutability. Consider this example…you need to write a method that takes in a List of integers as a parameter and the method needs to return the sum of all the odds numbers in the List. Simply enough, a C# method using a loop will look like this.

public int SumAllOdds(List<int> inputList)
{
    int result = 0;
    foreach (int number in inputList)
    {
        if (number % 2 == 1)
        {
            result += number;
        }
    }
    return result;
}

There’s nothing wrong with this, but the value of result variable is being modified within the loop. To ensure immutability, we have to come up with something else. I came up with a recursive method to do this, and this is as clean as I could get it to be.

public int SumAllOddsRecursive(List<int> inputList)
{
    if (inputList.Count == 1)
    {
        return (inputList[0] % 2 == 1) ? inputList[0] : 0;
    }
    return (inputList[0] % 2 == 1)
        ? inputList[0] + SumAllOddsRecursive(inputList.GetRange(1, inputList.Count - 1))
        : 0 + SumAllOddsRecursive(inputList.GetRange(1, inputList.Count - 1));
}

As you see, we are not modifying any values. In the recursion, we are using List.GetRange(index, count) method to get a new List of integers as we recurse to maintain immutability. It's not exactly very elegant code, maybe it's not a very good modification, but I promise you we will see improvements soon. :)

Functions as values

Functions as values is perhaps the highlight of functional programming. Functions are first class, and we can pass them around into other functions just as though they are simple variables. In C# 2.0 we have delegates, which is very much the same. In C# 3.0, we have new delegates types Func<T, TResult> and Action<T>, as well as Lambda Expressions which allow us to write code declaratively. Consider the previous example we used, and give it a slight twist. Instead of returning the sum of all odds numbers, I want to be able to use the same method to get the sum of all even numbers. Let’s refactor that…

public int SumAllRecursive(List<int> inputList, Func<int, bool> condition)
{
    if (inputList.Count == 1)
    {
        return (condition(inputList[0])) ? inputList[0] : 0;
    }
    return (condition(inputList[0]))
        ? inputList[0] + SumAllRecursive(inputList.GetRange(1, inputList.Count - 1), condition)
        : 0 + SumAllRecursive(inputList.GetRange(1, inputList.Count - 1), condition);
}
//calling the method using lambda expression to get even numbers
SumAllRecursive(list, new Func<int, bool>( i =>; i % 2 == 0))

We can pass in a delegate as a parameter into our method, and specify dynamically if we want the sum of all odd or even numbers. With the use of Lamba Expressions, you can write the delegate inline, saving you from having write a method. Let’s clean this up even further, by using some special methods that are part of the List<T> class. One such method is FindAll(Predicate<T> match) which return a new List with items that match the Predicate delegate you pass in. After another round of refactoring, we get this result.

public int SumAllWithPredicate(List<int> inputList, Predicate<int> condition)
{
    List<int> filtered = inputList.FindAll(condition);
    return filtered.Sum();
}

//calling the method using lambda expression to get even numbers
SumAllWithPredicate(temp, new Predicate<int>( i => i % 2 == 0));

The Sum() method is an extension method for IEnumerable<T> which adds up all items in the sequence, and is part of the LINQ . Isn’t the final result much cleaner and flexible. Finally let’s see the same thing translated in F#.

Translation into F#

  let numbers = [1..10]   (#1)
  let isOdd(n) = (n%2=1)  (#2)
  let newNumbers = List.filter isOdd numbers  (#3)
  let rec sumList(lst) =             (#4)
    match lst with                   (#5)
      | [] -> 0                      (#6)
      | hd::tl -> hd + sumList(tl)   (#7)

I jumped straight into it, because I think just by looking at the code, you can sort of understand most of it. It’s just that natural. Let’s break this down.

  • #1: declare (using let keyword) create a list of integers from 1 to 10.
  • #2: declare a function called isOdd that returns a boolean true if the n is odd.
  • #3: using List.filter (built-in function) passing it the isOdd function and numbers list, returning a new filtered list.
  • #4: declare a recursive function (rec keyword) called sumList that takes in a list
  • #5: using pattern matching (key feature in functional programming by using the match-with keyword, similar to switch in C#) with the list
  • #6: if list is empty (identified by []), return 0
  • #7: this one takes some explanation. hd = head and tl = tail. If pattern matches hd::tl which means list is not empty, take the first item (hd) and add it to the result of the recursion. We pass the tail (tl) of the list (minus the first item) to the recursion, hence going through every single item until the list is empty.

If you have noticed, we do not declare types in F#. The compiler infers that, and it’s really smart at doing that. For example, isOdd can only take in an integer and the compiler knows that because n%2 = 1 will only work with an integer. Consider sumList(lst), the compiler also knows that it can only take in a list, because of the pattern matching code we used which implies that the function is expecting a list. Also notice that we do not have to explicitly specify if a function returns a value, the compiler again infers that. Lastly, the F# code is structured by using indentation, unlike in C# where we use the {} braces.

These are some aspects of functional programming that I’m starting to appreciate and enjoy. It’s also natural to read and quick to understand, and very terse. I hope the C# examples has helped to make it easier to think more functionally, and understand the F# code. I intend to write more about F# once I drill more into it.

Download F# (May 2009 CTP) for VS2008. Allows you to create F# projects and use F# Interactive to execute F# code real-time.

Share this post :
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

%d bloggers like this: