Lambdas and Closures and Currying. Oh my! (Part 3)

In my previous post we went fairly deep into the syntax and use of lambda expressions in C# 3.0 and in this post we are going to discuss something that will make excellent use of those lambdas, higher order functions. Higher order functions are simply functions that can take functions as parameters and can also return functions as results. And I’m not talking about passing in the results of a function, or returning the results of a function. This is what we call function composition (you may remember the term from math class). Here is an example of function composition:

    //we declare a method that returns 5

    public static int iReturn5()

    {

        return 5;

    }

    //we declare a method that multiplies some number by 2

    public static int iMultiplyItBy2(int somenum)

    {

        return somenum * 2;

    }

    //now we compose these two functions to multiply 5 by 2

    public static int iMultiply5By2()

    {

        return iMultiplyItBy2(iReturn5());

    }

See, you are using these big fancy programming terms every day and you didn’t even know it! And no, you don’t need to stare at it any closer, I’m not tricking you or anything. I’m just showing you this so that I can compare it to higher order functions. Lets start off by showing you an example of a higher order function.

    public static TResult Fold<TArg, TResult>(IEnumerable<TArg> data, 

        Func<TArg, TResult, TResult> func, TResult result)

    {

        foreach (TArg i in data)

        {

            result = func(i, result);

        }

        return result;

    }

I know that this looks pretty ugly, so lets look at it closely and break it down. This is an example of a C# 3.0 implementation of the classic "Fold" higher order function (sometimes referred to as reduce), which iterates over something and accumulates the items. A classic example is adding up all of the integers in an integer array. So, lets start bu looking at the first parameter, which is "IEnumerable<TArg> data". This is pretty self explanatory, it is the item that you want to iterate over.

The second parameter "Func<TArg, TResult, TResult> func" is your reducing function. This function defines what you want to do with the items in the "data" argument (this will become more explanatory when I show you can example). It takes one parameter that is the type of the items in "data" and a second argument of the type you are accumulating, and then returns the accumulated type. So, if we were using int going in and string coming out (not sure why you would fold integers into a string, but just keep moving), its definition would look like this…

    public string func(int, string)

The last parameter "TResult result" is simply the seed for your reducing function, it is used to pass in what you have already accumulated up to this point. For example when starting with integers this would likely be zero, or with strings this would be String.Empty. Again, this will make more sense in a second. Here is an example of how you would call this with an array of integers:

    //declare our integer list

    var numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8 };

    //now pass in a reducing method that adds them up

    var result = Fold(numbers, (x, y) => x + y, 0);

We pass our list of integers into fold, and then our lambda that takes two parameters (the C# compiler can infer that these are integers since we are passing a zero as our third parameter) and then simply adds them together and returns an int. The first parameter is the next item in the list and the second parameter is the accumulated item so far. Our third parameter is "0", which is to simply get it started. We could even declare an overload of this method that automatically initializes the seed to "default(TResult)", which we will do below. (this is something that was added in C# 2.0 to support generics and initializes the generic parameter to its "default" value). We could also make this an extension method of IEnumerable that would look like this:

    public static TResult Fold<TArg, TResult>(

        this IEnumerable<TArg> data,

        Func<TArg, TResult, TResult> func, TResult result)

    {

      foreach (TArg i in data)

      {

        result = func(i, result);

      }

      return result;

    }

    public static TResult Fold<TArg, TResult>(

        this IEnumerable<TArg> data,

        Func<TArg, TResult, TResult> func)

    {

      return Fold(data, func, default(TResult));

    }

We have two functions here so that we can call it like this:

    var numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8 };

    var result = numbers.Fold((int x, int y) => x + y);

We have to add the "int" declarations back onto the lambda here because we are no longer passing a zero as the third parameter which no longer allows the C# compiler to figure out what type TResult is. We could make a more simple version of these methods that only takes one generic parameter, and that would make the type inference work, but then we would only be able to return the same type that we are passing in. Which would mean that we couldn’t use it with two types like this…

    var result = Fold(numbers, (x, y) => { y.Add(x); return y; }, 

        new System.Collections.ArrayList());

Being able to dump a List of numbers into an ArrayList is someone contrived, but you can see where I am going with this. You can use the Fold method to perform almost any operation on the items in your collection. I hope you can find some good uses for this, so until next time, have some fun with it! Leave a comment if you see anything that I have skimmed over that you would like to see elaborated in my next post.