Refactoring Towards the Y Combinator: Part 5

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

Here is the state of affairs at the end of part 4:

public delegate Factorial HigherOrderFactorial(Factorial factorial);

public class Solution07 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
                {
                    return x < 2 ? 1 : x * f(x - 1);
                };
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(self(self))(x);
            };
        };

        return factorial(factorial);
    }
}

As I mentioned at the end of part 4, the problem with this implementation is that the factorial function creates a closure, capturing the algorithm variable. I fixed a similar problem in step 2 – in this case its fixed by having the factorial function accept ‘algorithm’ as an argument. Unfortunately my first attempt at this will not compile:

SelfApplicable<Factorial> factorial = (HigherOrderFactorial alg, SelfApplicable<Factorial> self) =>
{
    return (int x) =>
    {
        return alg(alg, self(self))(x);
    };
};

return factorial(algorithm, factorial);

Its not that simple, because it breaks the signature of the SelfApplicable delegate. So I will have to define a new delegate. To figure out what to call it, lets take a look at its signature:

public delegate Factorial SomeDelegate(SomeDelegate self, HigherOrderFactorial algorithm);

So it takes itself, and a HigherOrderFactorial, and its returns a Factorial. Well in that case isn’t it fair to say that it is a “higher order evaluator”? Its also self applying, so lets call it SelfApplyingHigherOrderFactorialEvaluator:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

/// <summary>
/// We can make the algorithm an argument to the factorial function. Unfortunately its not a particularly simple refactoring, because of the
/// self calling nature of the factorial function. We are forced to define a new self applying delegate that accepts the higher order function.
/// </summary>
public class Solution08 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * f(x - 1);
            };
        };

        SelfApplyingHigherOrderFactorialEvaluator factorial =
            (SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial alg) =>
        {
            return (int x) =>
            {                            
                return alg(self(self, alg))(x);
            };
        };

        return factorial(factorial, algorithm);
    }
}

Phew! I was excited when this one worked – I could smell blood in the air. The body of that factorial function is starting to look pretty close to the Y combinator. Now I don’t know about you, but that factorial function is looking kind of hungry, so lets give it some curry! By currying it, I will have the opportunity to go back to using the SelfApplicable delegate. This is a tricky step, and I’m not quite sure how to break it down. I can start off by looking at the existing signature:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

I called this thing an evaluator, because it takes a HigherOrderFactorial, and it returns a Factorial. Essentially, it evaluates the higher order function which results in a normal order one. I could create a generic delegate to represent an evaluation operation, but to do so I would need to first create a generic delegate for representing a higher order function. Well that should be pretty straightforward:

public delegate T HigherOrderFunction<T>(T function);

The HigherOrderFunction delegate could be used instead of the HigherOrderFactorial delegate. Here is ‘algorithm’ modified to use the HigherOrderFunction delegate:

HigherOrderFunction<Factorial> algorithm = (Factorial f) =>
{
    return (int x) =>
    {
        return x < 2 ? 1 : x * f(x - 1);
    };
};

Now that I have a generic delegate for higher order functions, I can also create a generic delegate for their evaluation:

public delegate T HigherOrderEvaluator<T>(HigherOrderFunction<T> higherFunction);

Lets try to get comfortable with this before we move on. Lets say I used it like so:

HigherOrderEvaluator<Factorial> evaluator;

Then this is the same as (formatted for clarity):

Func<
    HigherOrderFunction<Factorial>, 
    Factorial
    > evaluator;

Which is the same as:

Func<
    Func<Factorial, Factorial>, 
    Factorial
    > evaluator;

I could expand out those Factorial delegates, but I do not think that is necessary. It would just cause an <int> explosion. Now that the HigherOrderEvaluator is defined and explained, I have the necessary tools to discuss how the SelfApplicableHigherOrderFactorialEvaluator is going to be replaced. Again, to make it easier to eyeball the changes, here it is:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

This delegate can be retired, because I can use this instead:

SelfApplicable<HigherOrderEvaluator<Factorial>>

BUT! I can only make that replacement if I curry the factorial method, as was discussed before. SelfApplicable only takes one argument, while you can see that the SelfApplyingHigherOrderFactorialEvaluator above takes two. Currying will allow me to reduce it to one argument, so I get to use SelfApplicable. Here is what it looks like:

public delegate T HigherOrderFunction<T>(T function);
public delegate T HigherOrderEvaluator<T>(HigherOrderFunction<T> higherFunction);

/// <summary>
/// Once again, we curry. This time its the factorial function again.
/// Believe it or not, the second function defined here is the Y combinator. Unfortunately, in this form it is specific to the factorial method..
/// </summary>
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 jumped out of my chair when this worked. I did a lap of my apartment, punching at the air. Yes, I am really that lame. ANYWAY…

The function that is still called ‘factorial’ is actually a version of the Y combinator specifically typed for being applied to factorials. In the final post for this series I will make it more general, clean it up, demonstrate it being used for Fibonacci and post the full source code.