*This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.*

This is the final part of my series on the Y combinator. By the end of part 5, the bulk of the work was done. All I have to do today is generalize it, clean it up and make it look pretty. Here is the code from part 5:

public class Solution09 : ISolution { public Factorial MakeFactorialFunction() { HigherOrderFunction<Factorial> algorithm = (Factorial f) => { return (int x) => { return x < 2 ? 1 : x * f(x - 1); }; }; SelfApplicable<HigherOrderEvaluator<Factorial>> factorial = (SelfApplicable<HigherOrderEvaluator<Factorial>> self) => { return (HigherOrderFunction<Factorial> alg) => { return (int x) => { return alg(self(self)(alg))(x); }; }; }; return factorial(factorial)(algorithm); } }

I claimed that the factorial function, as it is defined here, is a version of the Y combinator. Indeed if you take a look at it, you will see that it really doesn’t have anything to do with calculating factorials anymore – that code has long since been moved into the “algorithm” function. But the signature of the function still mentions factorials, specifically the Factorial delegate. To get my definition for the Y combinator into a more usable state, I can replace usages of the Factorial delegate with Func<int,int>. Later on, I’ll be able to define a generic version so it can even be used for functions that take and compute a double, or string, or whatever. However when I make this change, I still need to return a Factorial (because my test harness requires the MakeFactorialFunction method to return a Factorial delegate). To get around this I will use an earlier trick of returning a lambda that can be cast as a Factorial delegate:

/// <summary> /// Its possible to make a generic version of the Y combinator for application to functions that take 1 argument and return a value of the same type. /// Unfortunately we cannot continue to use the Factorial delegate if we want to make this generic version. /// We rename the functions to better represent their purpose (factorial becomes Y, algorithm becomes factorial). /// We can't just return Y(Y)(factorial)(x) because that will return a Func<int,int> but this method is supposed to return a Factorial. Although /// they are basically the same thing, a conversion cannot be made. Therefore I have to return a lambda that calls Y(Y)(factorial)(x). /// </summary> public class Solution10 : ISolution { public Factorial MakeFactorialFunction() { HigherOrderFunction<Func<int, int>> factorial = (Func<int, int> f) => { return (int x) => { return x < 2 ? 1 : x*f(x - 1); }; }; SelfApplicable<HigherOrderEvaluator<Func<int, int>>> Y = (SelfApplicable<HigherOrderEvaluator<Func<int, int>>> self) => { return (HigherOrderFunction<Func<int, int>> alg) => { return (int x) => { return alg(self(self)(alg))(x); }; }; }; return x => { return Y(Y)(factorial)(x); }; } }

I can now make Y generic by moving it into its own generic class:

/// <summary> /// Move Y into its own class. /// </summary> public class Solution11 : ISolution { public Factorial MakeFactorialFunction() { HigherOrderFunction<Func<int, int>> factorial = (Func<int, int> f) => { return (int x) => { return x < 2 ? 1 : x * f(x - 1); }; }; return x => { return YCombinator<int>.Y(YCombinator<int>.Y)(factorial)(x); }; } private static class YCombinator<T> { public static SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y = (SelfApplicable<HigherOrderEvaluator<Func<T, T>>> self) => { return (HigherOrderFunction<Func<T, T>> alg) => { return (T x) => { return alg(self(self)(alg))(x); }; }; }; } }

There is some ugliness with calling Y on itself now, so I add a “ApplyY” helper to the YCombinator class to make this part easier. I let Resharper help me use a more terse syntax for the lambdas, and this is the result:

public class YCombinator<T> { private static readonly SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y = self => algorithm => t => algorithm(self(self)(algorithm))(t); public static readonly HigherOrderEvaluator<Func<T, T>> ApplyY = Y(Y); }

I’ve avoided using the terse lambda syntax up until now because I think it would have made comprehending the individual steps more difficult. I can use ApplyY like this:

return YCombinator<int>.ApplyY(factorial)(10);

Here is my final implementation for this entire exercise, utilizing the above class:

/// <summary> /// This is the final implementation. /// The Y combinator has been moved to a separate file. /// The factorial algorithm has been pushed to a static member and condensed. /// </summary> public class Solution12 : ISolution { private static readonly HigherOrderFunction<Func<int, int>> factorial = f => x => x < 2 ? 1 : x * f(x - 1); public Factorial MakeFactorialFunction() { return x => YCombinator<int>.ApplyY(factorial)(x); } // Example of using Y without any need for the Factorial delegate: public int CalculateFactorialOf10() { return YCombinator<int>.ApplyY(factorial)(10); } }

Now lets test my implementation of the Y combinator by using it to calculate Fibonacci numbers:

public static class Fibonacci { private static readonly HigherOrderFunction<Func<int, int>> fibonacci = f => x => x < 3 ? 1 : f(x - 1) + f(x - 2); public static int Calculate(int nthNumber) { return YCombinator<int>.ApplyY(fibonacci)(nthNumber); } }

Its horribly inefficient, but it works:

Console.WriteLine(Fibonacci.Calculate(10));

So there you have it: the Y combinator implemented in C#, derived via many gradual refactorings. This implementation still has some limitations. For example, it won’t support a recursive algorithm that takes two arguments. You could of course modify the Y combinator class to support this, but because of the strongly typed nature of C#, it seems very difficult to make a definition of Y that could be applied to an algorithm with ANY signature. If you are interested in exploring the code that I provided in this series, you can download it here.

I really enjoyed this exercise and I would definitely encourage other programmers that are weak at functional programming to have a go at it. If you really know this stuff and my clumsy explanations made you cringe, please leave a comment! If you were following along with the series and got lost or stuck at some point, again, please comment! Practice makes perfect, but some constructive criticism can really help too. Thanks!