Refactoring Towards the Y Combinator: Part 6

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));

>> 55

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!