Archive for April, 2010

Refactoring To Functional Code

In my previous post I explained that some problems are better suited to a functional approach than traditional, imperative code. I showed an example of a problem that suits a functional approach and demonstrated turning several lines of imperative code with nested for-each loops and if-statements into a single line of functional code. Paul Harrington posted a comment asking what individual steps I took to refactor the code. Here’s my explanation of the refactoring:

First, here is the original, imperative method.

public int[] Translate(string word)
{
    ArrayList numbers = new ArrayList();

    foreach (char character in word)
    {
        foreach(KeyValuePair<int, char[]> key in keys)
        {
            foreach(char c in key.Value)
            {
                if(c == character)
                {
                    numbers.Add(key.Key);
                }
            }
        }
    }

    return (int[]) numbers.ToArray(typeof (int));
}

As you can see, it takes some effort to determine what’s really going on. From this code we can determine that:

For each character in a word, select the first key in the list of keys that contains the character and add it to an array of numbers to return.

Now, lets express the statement above as functional code:

To select each character in a word, we need to convert the string to an array of characters. The LINQ Select method projects each element of a sequence into a new form. In this case, a string translates to a sequence of characters:

IEnumerable<char> characters = word.Select(c => c);

For each character, we need to find the corresponding key that contains the character. The First method returns the first element of a sequence:

int key = keys.First().Key;

In our case we need the first key in the list of keys that contains the character. The First method has an overload that returns the first element in a sequence that satisfies a specified condition.  To specify our condition we use the Contains method, which determines whether a sequence contains a specified element:

char c = 'a';
int number = keys.First(k => k.Value.Contains(c)).Key;

When we combine the code that selects each character with the code that gets the first key containing the character, we end up with this:

IEnumerable<int> numbers = word.Select(c =>
        keys.First(k => k.Value.Contains(c)).Key);

Finally, we use the ToArray method to return an array of type int. Now we have our final, refactored method:

public int[] Translate(string word)
{
    return word.Select(c =>
        keys.First(k => k.Value.Contains(c)).Key).ToArray();
}

I hope this helps to explain the steps I took to refactor imperative code to functional code. You can get really clever with functional code, but remember, readability is what’s most important. Sometimes it’s best to stick with good old-fashioned for-loops and if-statements, but for some problems, like above, a functional approach can lead to more readable, clean and concise code.

An Example of Functional vs Imperative Programming in C#

Last week I went to a talk presented by Mike Wagg and Mark Needham from ThoughtWorks on Mixing Functional and Object-Oriented Approaches to Programming in C#. Mike and Mark discussed using a functional approach with LINQ to solve problems in C#.

I have come to realise lately that some problems are much better suited to a functional approach than traditional imperative programming. Many problems that involve selecting, filtering or performing actions on a list of items are best suited to functional programming, which can significantly reduce the amount of code required to solve the problem.

Here is a simple example of a problem that is best solved with a functional rather than an imperative approach.

Some businesses advertise their phone number as a word, phrase or combination of numbers and alpha characters. This is easier for people to remember than a number. You simply dial the numbers on the keypad that correspond to the characters. For example, “1-800 FLOWERS” translates to 1-800 3569377.

We will write a simple program that translates a word into a list of corresponding numbers.

phone-keypad

First, let’s start with a dictionary that contains each number and the corresponding characters:

private readonly Dictionary<int, char[]> keys =
            new Dictionary<int, char[]>()
                {
                    {1, new char[] {}},
                    {2, new[] {'a', 'b', 'c'}},
                    {3, new[] {'d', 'e', 'f'}},
                    {4, new[] {'g', 'h', 'i'}},
                    {5, new[] {'j', 'k', 'l'}},
                    {6, new[] {'m', 'n', 'o'}},
                    {7, new[] {'p', 'q', 'r', 's'}},
                    {8, new[] {'t', 'u', 'v'}},
                    {9, new[] {'w', 'x', 'y', 'z'}},
                    {0, new[] {' '}},
                };

Next, we create a Translate method that takes a word and returns an array of corresponding numbers.

With a traditional, imperative approach, we would use for-each loops and if-statements to iterate through characters and populate an array of matching numbers:

public int[] Translate(string word)
{
    ArrayList numbers = new ArrayList();

    foreach (char character in word)
    {
        foreach(KeyValuePair<int, char[]> key in keys)
        {
            foreach(char c in key.Value)
            {
                if(c == character)
                {
                    numbers.Add(key.Key);
                }
            }
        }
    }

    return (int[]) numbers.ToArray(typeof (int));
}

Alternatively, with a functional approach we can use LINQ to select elements from the dictionary and transform the output to an array of matching numbers:

public int[] Translate(string word)
{
    return word.Select(c => 
        keys.First(k => k.Value.Contains(c)).Key).ToArray();
}

And there you have it. Several lines of nested for-each loops replaced with a single line of succinct functional code. Much nicer!