If you are new to this series, start here.

Before I move on to the two remaining items on my list (pattern matching and memoization), I’d like to take a brief excursion and talk about about Linq in C#. I never said it explicitly, but I have been writing this series for C# developers. I do plan to show you more F#, but while reading the aforementioned Real World Functional Programming I found it very helpful to first learn these concepts in a familiar language.

Linq is Functional

You might have heard it mentioned that Linq was born from the influence of functional languages. Let’s take a moment and connect some dots.

It the last post, I gave you a functional version of our Reduce function. However, both the imperative version and the functional version were tied to working just with integers.

Now you might have notice that these specific implementations can be abstracted into the concept of reducing a list of items of a certain type to a single item of the same time.

Starting with our imperative version, we just need to replace all of the ints with a generic type parameter:

// generic imperative version
static T Reduce<T>(Func<T, T, T> reducer, IEnumerable<T> values)
{


T accum = default(T);
foreach (var i in values)
{
    accum = reducer(accum, i);
}
return accum;


}

Well, we’d also have to initialize the accum variable a bit differently.

A generic version of the functional one is

static T ReduceF<T>(Func<T, T, T> reducer, IEnumerable<T> values, T seed)
{
    if (!values.Any()) return seed;

    var first = values.First();
    var remainder = values.Skip(1);
    var next = reducer(seed, first);

    return ReduceF(reducer, remainder, next);
}

or even better

static T ReduceF(Func<T, T, T> reducer, IEnumerable<T> values, T seed)   
{   
    return values.Any()    
        ? ReduceF(reducer, values.Skip(1), reducer(seed, values.First()))    
        : seed;   
}  

Now, in C# would could save even more typing by implementing our Reduce using Linq

static T ReduceLinq<T>(Func<T, T, T> reducer, IEnumerable<T> values)
{
    return values.Aggregate(default(T), reducer);
}

Of course, after we do, we realize that our Reduce function is the same as the Aggregate extension method that already exists in Linq!

You see, if you are using Linq then you are already utilizing functional language concepts.

N.B. The implementations of ReduceF are not something that you’d want to use in practice. Even though I followed a tail call style for the recursion, you’d still end up with a stack overflow in C#.

Removing the Extra Parameter

Of course, the functional version ReduceF still has that extra parameter that we named seed. We’d like to get rid of that.

The approach that I have frequently seen, is to wrap the recursion function in another function that provides the initial state. In other words, we’d leave ReduceF as it is (though we’d likely make it private) and then we’d add a new function that looked like this:

static T ReducePublic<T>(Func<T, T, T> reducer, IEnumerable<T> values)
{
    return ReduceF<T>(reducer, values, default(T));
}

Update: there is some good discussion about removing the extra parameter in the comments of part 3. As mentioned there, the primary reason for doing it this way is an academic desire to preserve the tail call form.

In our next post, we’ll start digging a little deeper into F#.