This is the seventh article in my series that aims to explain functional programming ideas using C#. Originally, I had planned to use only C# 2.0 for code examples, but have abandoned that aspiration in favor of the clarity achieved through C# 3.0's type inference. I should mention that all of the code examples could be rewritten in C# 2.0. However, now I am leaving that as an exercise for the reader.

As always, if this series is new for you, please feel free to check out the previous articles:

1. Fibonacci Numbers, Caching and Closures
2. What's in a Closure?
3. Using Automatic Memoization
4. A Higher Calling
5. The Art of Currying
6. Building Functions from Functions, part 1: Partial Application

In particular, articles 2, 4, 5 and 6 are helpful for understanding the material presented here.

Previously on Did It With .Net...

Last time, we attempted to use currying and partial application to build the factorial function from the Reduce and Sequence higher-order functions. We came pretty close to what we wanted.

While we managed to calculate the factorial of 10, we didn't quite produce the factorial function. There is one missing concept that must be introduced before we can finish. Before we look at it, let's review what we have done so far.

A Recap

The first step in building the factorial function is to create a function that will calculate the product of a sequence of numbers, represented by an IEnumerable<Int64>. This is done by the first two statements in the code example above. Currying the Reduce higher-order function and then partially applying the first two arguments give us the function we need, as the following diagram illustrates.

Let's dissect the code a bit further to demonstrate how the delegates are manipulated to create the getProduct() function.

The comments show the underlying delegate types produced by each statement. The delegate types can be pretty gnarly, so feel free to ignore them. After all, that's why we're using C# 3.0's "var" keyword. Here is what each statement in this code sample does:

1. The GetReduce() helper method is called to retrieve a delegate for Reduce.
2. The Reduce delegate is curried.
3. The first argument of the curried Reduce delegate, the accumulator function, is partially applied. Because this argument requires a delegate, we use a lambda expression that takes two parameters and returns their product.
4. The second argument of the curried Reduce delegate, the starting value, is partially applied. Since the function will be performing multiplication, the starting value is one.

Once we have a function for calculating the product of a sequence of numbers, the next step is to create a function that produces the sequence we'll use. To properly calculate factorial, this should be a sequence of natural numbers starting from one. Again, we use currying and partial application to manipulate an existing higher-order function to produce the natural-number sequence. This time, the higher-order function we'll use is Sequence.

Sequence is a fairly simple function. It might look a bit more complicated than it is because Sequence is very general; it can produce a sequence of anything. In addition, the use of a C# iterator might be new to some of you. If that's the case, take a look at what Wikipedia has to say about generators and coroutines.

Looking closer, Sequence takes just three arguments:

1. A function that is called to retrieve the next value in the sequence.
2. A starting value for the sequence.
3. A function that is called to determine when (if ever) the sequence should end.

The following diagram shows how currying are partial application are used to manipulate Sequence's signature.

Like before, the following breakdown of the code shows how the underlying delegates are manipulated to produce the naturalsFromOne() function.

Let's look at what is happening in each statement.

1. The GetSequence() helper method is called to retrieve a delegate for Sequence.
2. The Sequence delegate is curried.
3. The first argument of the curried Sequence delegate, the next value function, is partially applied. Because this argument requires a delegate, we use a lambda expression that takes one parameter and returns its increment.
4. The second argument of the curried Sequence delegate, the starting value, is partially applied. Since the function will return a sequence of natural numbers, the starting value is one.

With the two functions that we have created, getProduct() and naturalsFromOne(), we can successfully calculate factorial.

While this calculation is faithful, it really isn't what we're looking for. Somehow, we need to transform this:

Into this:

Currying and partial application only take us so far. To complete the sample we need to discuss...

The Dark Art of Function Composition

OK. Function composition isn't all that dark. In fact, the idea is pretty simple. When one function is called with the result of another function, those two function calls can be composed, or combined, into a single function.

Let's consider function composition in the abstract. Suppose we have a function, F1, that takes a parameter of type A and returns a value of type B. In addition, we have a function, F2, that takes a parameter of type B and returns a value of type C.

• F1(A) : B
• F2(B) : C

Given a value of type A, we would need to call F2 with the result of calling F1 in order to calculate a value of type C.

• C = F2(F1(A))

It really is that simple. Translating this abstract example into a general Compose function is easy:

Now that we have a way to compose functions, we should be able to create factorial like this:

Well, not quite. This is definitely an improvement, but the argument isn't right. Instead of passing in a number, we have to pass in a function. At this point, the argument of factorial() is actually the shouldStop() argument from the naturalsFromOne() function. We'd like to call factorial(10), but instead, we have to call it like this:

How can we can fix this? The solution is to compose naturalsFromOne() with another function. This additional function will take a number as an argument and return a function that can be used as the shouldStop() argument of naturalsFromOne().

The additional function should have the following signature:

• additionalFunction(Int64) : Func<Int64, Boolean>

Which should be composed with naturalsFromOne():

• naturalsFromOne(Func<Int64, Boolean>) : IEnumerable<Int64>

Once this is done, we can compose our newly-composed naturalsFromOne() function with getProduct() to produce the factorial function.

But we're getting ahead of ourselves. Here is how we can define the additional function, whose destiny is to be composed with naturalsFromOne().

Looking carefully at the double-arrow-lambda-expression-thingy, we can see that this is actually the curried version of a function with a signature of (Int64, Int64) : Boolean.

In fact, that method already exists in the .NET Framework: System.Collections.Generic.EqualityComparer<Int64>.Equals(). Instead of declaring this function ourselves, we can curry the existing Framwork API.

After currying, we have a function that takes an Int64 and returns a Func<Int64, Boolean>. We can compose this with naturalsFromOne(), and compose that with getProduct(). The result is the factorial() function that we've been searching for.

Inserting this into the original code example completes it.

We've finally done what we set out to do. We have built new functions using only general, pre-existing functions as building blocks and currying, partial application and function composition as tools. As I've stated before, this is truly the meat-and-potatoes of functional programming.

There's more to come. Stay tuned!