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:
- Fibonacci Numbers, Caching and Closures
- What's in a Closure?
- Using Automatic Memoization
- A Higher Calling
- The Art of Currying
- 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.
static void Main()
{
var reduce = HigherOrder.GetReduce<Int64>().Curry();
var getProduct = reduce((x, y) => x * y)(1);
var sequence = HigherOrder.GetSequence<Int64>().Curry();
var naturalsFromOne = sequence(x => ++x)(1);
var factorialOf10 = getProduct(naturalsFromOne(x => x == 10));
Console.WriteLine("Factorial of 10 is {0:#,#}", factorialOf10);
}
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.
static void Main()
{
// Original Code:
// var reduce = HigherOrder.GetReduce<Int64>().Curry();
// var getProduct = reduce((x, y) => x * y)(1);
// 1. Func<Func<Int64, Int64, Int64>, Int64, IEnumerable<Int64>, Int64>
var reduce = HigherOrder.GetReduce<Int64>();
// 2. Func<Func<Int64, Int64, Int64>, Func<Int64, Func<IEnumerable<Int64>, Int64>>>
var curriedReduce = reduce.Curry();
// 3. Func<Int64, Func<IEnumerable<Int64>, Int64>>
var multiply = curriedReduce((x, y) => x * y);
// 4. Func<IEnumerable<Int64>, Int64>
var getProduct = multiply(1);
}
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:
- The GetReduce() helper method is called to retrieve a delegate for Reduce.
- The Reduce delegate is curried.
- 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.
- 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.
public static IEnumerable<T> Sequence<T>(Func<T, T> getNext, T startValue, Func<T, Boolean> shouldStop)
{
if (getNext == null)
yield break;
T value = startValue;
yield return value;
while (true)
{
if (shouldStop != null && shouldStop(value))
break;
value = getNext(value);
yield return value;
}
}
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:
- A function that is called to retrieve the next value in the
sequence.
- A starting value for the sequence.
- 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.
static void Main()
{
// Original Code:
// var sequence = HigherOrder.GetSequence<Int64>().Curry();
// var numbersFromOneToX = sequence(x => ++x)(1);
// 1. Func<Func<Int64, Int64>, Int64, Func<Int64, Boolean>, IEnumerable<Int64>>
var sequence = HigherOrder.GetSequence<Int64>();
// 2. Func<Func<Int64, Int64>, Func<Int64, Func<Func<Int64, Boolean>, IEnumerable<Int64>>>>
var curriedSequence = sequence.Curry();
// 3. Func<Int64, Func<Func<Int64, Boolean>, IEnumerable<Int64>>>
var numberSequence = curriedSequence(x => ++x);
// 4. Func<Func<Int64, Boolean>, IEnumerable<Int64>>
var naturalsFromOne = numberSequence(1);
}
Let's look at what is happening in each statement.
- The GetSequence() helper method is called to retrieve a delegate for
Sequence.
- The Sequence delegate is curried.
- 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.
- 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.
var factorialOf10 = getProduct(naturalsFromOne(x => x == 10));
Console.WriteLine("Factorial of 10 is {0:#,#}", factorialOf10);
While this calculation is faithful, it really isn't what we're looking for.
Somehow, we need to transform this:
var factorialOf10 = getProduct(naturalsFromOne(x => x == 10));
Into this:
var factorialOf10 = factorial(10);
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.
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.
It really is that simple. Translating this abstract example into a general Compose function
is easy:
public static Func<A, C> Compose<A, B, C>(
Func<A, B> f1,
Func<B, C> f2)
{
return a => f2(f1(a));
}
Now that we have a way to compose functions, we should be able to create
factorial like this:
var factorial = HigherOrder.Compose(naturalsFromOne, getProduct);
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:
var factorialOf10 = factorial(x => x == 10);
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().
Func<Int64, Func<Int64, Boolean>> equals = x => y => x == y;
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.
Func<Int64, Int64, Boolean> equals = (x, y) => x == y;
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.
Func<Int64, Int64, Boolean> equals = EqualityComparer<Int64>.Default.Equals;
var curriedEquals = equals.Curry();
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.
var naturalsFromOneToX = HigherOrder.Compose(equals, naturalsFromOne);
var factorial = HigherOrder.Compose(naturalsFromOneToX, getProduct);
var factorialOf10 = factorial(10);
Inserting this into the original code example completes it.
static void Main()
{
var reduce = HigherOrder.GetReduce<Int64>().Curry();
var getProduct = reduce((x, y) => x * y)(1);
var sequence = HigherOrder.GetSequence<Int64>().Curry();
var naturalsFromOne = sequence(x => ++x)(1);
var equals = HigherOrder.GetEquals<Int64>().Curry();
var naturalsFromOneToX = HigherOrder.Compose(equals, naturalsFromOne);
var factorial = HigherOrder.Compose(naturalsFromOneToX, getProduct);
var factorialOf10 = factorial(10);
Console.WriteLine("Factorial of 10 is {0:#,#}", factorialOf10);
}
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!